Introducción a la teoría de matroides

Abstract

En este trabajo se hace una introducción a la teoría de Matroides. Se presentarán algunas de las definiciones más usadas para referirse a una matroide, donde se incluyen resultados de la teoría de grafos, transversalese independencia lineal, todas ellas como sistemas axiomáticos. Mostraremos que todas estas definiciones son equivalentes, fenómeno conocido como criptomorfismo. También se mostrará una aplicación de la teoría de Matroides para solucionar problemas de optimización sobre grafos (algoritmo Greedy). En el primer capítulo se presentan los conceptos básicos de la teoría de grafos, espacios vectoriales y teoría de transversales, estos resultados serán utilizados para definir Matroides; en el segundo capítulo mostraremos los diferentesmodos de definir Matroides sin perder la esencia de la independencia lineal introducida por Whitney. Para finalizar, enel tercer capítulo, mostraremos la aplicación más conocida en la teoría de matroides, que permite solucionar algunos delos problemas de optimización sobre grafos, en este caso los problemas de optimización más usados son de maximizaro minimizar, donde el algoritmo que usaremos es óptimo cuando cumple los axiomas que definen a una matroide, encaso contrario el algoritmo no es óptimo. La forma como organizamos la presentación de este trabajo permite comprender de una manera sencilla la noción del termino matroide y su importancia en aplicaciones de optimización sobre grafos.