## [Matroide](/es/node/61161) Definición Una estructura combinatoria (E, I) sobre un conjunto finito E con una familia I de subconjuntos independientes que satisfacen axiomas (herencia e intercambio) que abstraen la independencia lineal en espacios vectoriales y la ausencia de ciclos en grafos. ## Principio Principio La independencia es estable por paso a subconjuntos (herencia) y satisface la propiedad de intercambio: si A y B son independientes con |A|>|B| entonces existe un elemento de A\B que puede añadirse a B conservando la independencia; formulaciones equivalentes usan bases, función rango o circuitos y permiten la dualidad del matroide. ## Demostración Demostración Matroide vectorial: las columnas de una matriz sobre un cuerpo forman un matroide cuyo conjuntos independientes son los subconjuntos de columnas linealmente independientes. Matroide gráfico: las aristas de un grafo forman un matroide cuyos conjuntos independientes son los bosques y cuyos circuitos son ciclos simples. ## Aplicación incorrecta Aplicación incorrecta Asumir que todo matroide es representable sobre un campo dado (muchos matroides no lo son), o tratar sistemas arbitrarios de conjuntos con conjuntos independientes máximos como matroides sin comprobar el axioma de intercambio. ## Consecuencia Consecuencia La estructura de matroide asegura que el algoritmo codicioso encuentra soluciones óptimas para la maximización ponderada de conjuntos independientes, proporciona operadores de rango y cierre para optimización combinatoria y soporta dualidad y operaciones de menores que reflejan menores de grafos y restricción/contracción lineales. ## Inversión Inversión Invertir el concepto conduce a considerar sistemas de independencia arbitrarios que carecen de la propiedad de intercambio: tales sistemas pueden tener múltiples conjuntos independientes máximos incomparables y fallar en la optimalidad codiciosa, perdiendo los teoremas estructurales fuertes de la teoría del matroide. ## Límite Límite La teoría estándar trata conjuntos finitos aunque existen matroides infinitos con axiomas adicionales; los matroides excluyen sistemas de conjuntos que violan intercambio, y la representabilidad depende del campo elegido, de modo que las correspondencias algebraicas no son universales. ## Tensión semántica Tensión semántica Tensión entre matroides abstractos y matroides representables (lineales): muchos resultados combinatorios solo requieren los axiomas de matroide, pero los métodos algebraicos y la intuición geométrica se aplican solo a matroides representables; los matroides gráficos y cográficos muestran perspectivas duales. ## Síntesis Síntesis Un matroide abstrae el núcleo combinatorio de la independencia codificando qué subconjuntos de un conjunto finito se comportan como conjuntos linealmente independientes mediante herencia e intercambio, ofreciendo un marco unificado para optimización, dualidad, menores y conexiones entre teoría de grafos y álgebra lineal.