RT info:eu-repo/semantics/bachelorThesis
T1 El problema de la intersección de matroides
A1 Blázquez Hernández, María
A2 Universidad de Valladolid. Facultad de Ciencias
K1 Matroide
K1 Optimización combinatorial
AB En este trabajo, se estudia la dependencia de forma abstracta a través de los matroides, centrándose más en la intersección de dos matroides. En primer lugar, se empieza con una introducción sobre el concepto de matroide. A continuación, se trata el tema central del trabajo, que es encontrar un conjunto independiente de máxima cardinalidad común a dos matroides, así como un conjunto independiente de máximo peso común a dos matroides, respecto a una función de coste. Primero, se estudia la búsqueda de un conjunto independiente de máximo peso respecto a una función de coste en un matroide, lo cual se lleva a cabo a través del algoritmo voraz. Después se introduce una relación entre matroides y politopos que permite obtener resultados importantes en la intersección de dos matroides. También se incluye un algoritmo a través del cual se obtiene tal conjunto deseado común a dos matroides. Por último, se añaden algunas aplicaciones de intersección de dos matroides y se expone un poco la intersección de más matroides.
YR 2019
FD 2019
LK http://uvadoc.uva.es/handle/10324/43366
UL http://uvadoc.uva.es/handle/10324/43366
LA spa
DS UVaDOC
RD 19-oct-2024