matriz gráfica
En la teoría matemática de las matroides , una matroide gráfica (también llamada matroide de ciclo o matroide poligonal ) es una matroide cuyos conjuntos independientes son los bosques en un grafo no dirigido finito dado . Las matroides duales de matroides gráficas se denominan matroides co-gráficas o matroides de unión . [1] Una matroide que es a la vez gráfica y cográfica se denomina matroide plana ; estos son exactamente los matroides gráficos formados a partir de gráficos planos .
Un matroide puede definirse como una familia de conjuntos finitos (llamados "conjuntos independientes" del matroide) que está cerrado en subconjuntos y que satisface la "propiedad de intercambio": si los conjuntos y son independientes y son más grandes que , entonces no es un elemento tal que permanece independiente. Si es un grafo no dirigido, y es la familia de conjuntos de aristas que forman bosques en , entonces está claramente cerrado bajo subconjuntos (eliminar aristas de un bosque deja otro bosque). También satisface la propiedad de intercambio: si y son ambos bosques, y tiene más aristas que , entonces tiene menos componentes conexas, por lo que por laprincipio del casillero hay un componente de que contiene vértices de dos o más componentes de . A lo largo de cualquier camino desde un vértice en un componente hasta un vértice de otro componente, debe haber una arista con extremos en dos componentes, y esta arista se puede agregar para producir un bosque con más aristas. Así, forma los conjuntos independientes de un matroide, llamado matroide gráfico de o . De manera más general, una matroide se llama gráfico siempre que sea isomorfa a la matroide gráfica de un gráfico, independientemente de si sus elementos son bordes en un gráfico. [2]
