El problema de la intersección de matroides

Abstract

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.