Matroid gráfico

En la teoría matemática de los matroides , un matroide gráfico (también llamado matroide cíclico o matroide poligonal ) es un matroide cuyos conjuntos independientes son los bosques en un grafo finito no dirigido dado . Los matroides duales de los matroides gráficos se llaman matroides cográficos o matroides de enlace . ^{[ 2 ]} Un matroide que es a la vez gráfico y cográfico se llama a veces matroide planar (pero esto no debe confundirse con los matroides de rango 3, que generalizan configuraciones de puntos planares); estos son exactamente los matroides gráficos formados a partir de grafos planares .

Un matroide puede definirse como una familia de conjuntos finitos (llamados los "conjuntos independientes" del matroide) que es cerrada bajo subconjuntos y que satisface la "propiedad de intercambio": si los conjuntos${\displaystyle A}$y${\displaystyle B}$son ambos independientes y${\displaystyle A}$es más grande que${\displaystyle B}$, entonces hay un elemento${\displaystyle x\in A\setminus B}$de tal manera que${\displaystyle B\cup \{x\}}$permanece independiente. Si${\displaystyle G}$es un grafo no dirigido y${\displaystyle F}$es la familia de conjuntos de bordes que forman bosques en${\displaystyle G}$, entonces${\displaystyle F}$es claramente cerrado bajo subconjuntos (eliminar aristas de un bosque deja otro bosque). También satisface la propiedad de intercambio: si${\displaystyle A}$y${\displaystyle B}$son ambos bosques, y${\displaystyle A}$tiene más bordes que${\displaystyle B}$, entonces tiene menos componentes conectados, por lo que por el principio del palomar hay un componente${\displaystyle C}$de${\displaystyle A}$que contiene vértices de dos o más componentes de${\displaystyle B}$. A lo largo de cualquier camino en${\displaystyle C}$desde un vértice en un componente de${\displaystyle B}$a un vértice de otro componente, debe haber una arista con puntos finales en dos componentes, y esta arista puede agregarse a${\displaystyle B}$para producir un bosque con más bordes. Por lo tanto,${\displaystyle F}$forma los conjuntos independientes de un matroide, llamado matroide gráfico de${\displaystyle G}$o${\displaystyle M(G)}$. De manera más general, un matroide se denomina gráfico siempre que sea isomorfo al matroide gráfico de un grafo, independientemente de si sus elementos son aristas en un grafo. ^{[ 3 ]}

Las bases de un matroid gráfico${\displaystyle M(G)}$son los bosques que se extienden por completo${\displaystyle G}$y los circuitos de${\displaystyle M(G)}$son los ciclos simples de${\displaystyle G}$. El rango en${\displaystyle M(G)}$de un conjunto${\displaystyle X}$de aristas de un grafo${\displaystyle G}$es${\displaystyle r(X)=nc}$dónde${\displaystyle n}$es el número de vértices en el subgrafo formado por las aristas en${\displaystyle X}$y${\displaystyle c}$es el número de componentes conexas del mismo subgrafo. ^{[ 3 ]} El corango del matroide gráfico se conoce como rango de circuito o número ciclomático.

El cierre${\displaystyle \operatorname {cl} (S)}$de un conjunto${\displaystyle S}$de bordes en${\displaystyle M(G)}$es un plano que consta de los bordes que no son independientes de${\displaystyle S}$(es decir, los bordes cuyos extremos están conectados entre sí por un camino en${\displaystyle S}$). Este plano puede identificarse con la partición de los vértices de${\displaystyle G}$en los componentes conectados del subgrafo formado por${\displaystyle S}$: Cada conjunto de aristas que tienen el mismo cierre que${\displaystyle S}$da lugar a la misma partición de los vértices, y${\displaystyle \operatorname {cl} (S)}$puede recuperarse de la partición de los vértices, ya que consiste en las aristas cuyos extremos pertenecen al mismo conjunto en la partición. En la red de planos de este matroide, hay una relación de orden${\displaystyle x\leq y}$siempre que la partición correspondiente a plano ${\displaystyle x}$es un refinamiento de la partición correspondiente a plano ${\displaystyle y}$.

En este aspecto de los matroides gráficos, el matroid gráfico para un gráfico completo${\displaystyle K_{n}}$es particularmente importante, porque permite que cada partición posible del conjunto de vértices se forme como el conjunto de componentes conexas de algún subgrafo. Por lo tanto, la red de planos del matroide gráfico de${\displaystyle K_{n}}$es naturalmente isomorfo a la red de particiones de un${\displaystyle n}$Conjunto de elementos . Dado que las retículas de planos de matroides son exactamente las retículas geométricas , esto implica que la retícula de particiones también es geométrica. ^{[ 4 ]}

El matroide gráfico de un gráfico${\displaystyle G}$puede definirse como el matroide columna de cualquier matriz de incidencia orientada de${\displaystyle G}$Dicha matriz tiene una fila por cada vértice y una columna por cada arista. La columna para la arista${\displaystyle e}$tiene${\displaystyle +1}$en la fila para un punto final,${\displaystyle -1}$en la fila para el otro punto final, y${\displaystyle 0}$En otros casos, la elección de qué extremo asignar qué signo es arbitraria. El matroide columna de esta matriz tiene como conjuntos independientes los subconjuntos linealmente independientes de columnas.

Si un conjunto de aristas contiene un ciclo, entonces las columnas correspondientes (multiplicadas por${\displaystyle -1}$si es necesario reorientar los bordes de manera consistente alrededor del ciclo) suman cero y no son independientes. Por el contrario, si un conjunto de bordes forma un bosque, entonces al eliminar repetidamente hojas de este bosque se puede demostrar por inducción que el conjunto correspondiente de columnas es independiente. Por lo tanto, la matriz de columnas es isomorfa a${\displaystyle M(G)}$.

Este método de representación de matroides gráficos funciona independientemente del campo sobre el que se define la incidencia. Por lo tanto, los matroides gráficos forman un subconjunto de los matroides regulares , matroides que tienen representaciones sobre todos los campos posibles. ^{[ 3 ]}

La red de planos de un matroide gráfico también puede realizarse como la red de una disposición de hiperplanos , de hecho como un subconjunto de la disposición de trenzas , cuyos hiperplanos son las diagonales.${\displaystyle H_{ij}=\{(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}\mid x_{i}=x_{j}\}}$. Es decir, si los vértices de${\displaystyle G}$son${\displaystyle v_{1},\ldots,v_{n},}$incluimos el hiperplano${\displaystyle H_{ij}}$cuando sea${\displaystyle e=v_{i}v_{j}}$es un borde de${\displaystyle G}$.

Se dice que un matroide es conexo si no es la suma directa de dos matroides más pequeños; es decir, es conexo si y solo si no existen dos subconjuntos disjuntos de elementos tales que la función de rango del matroide sea igual a la suma de los rangos de estos subconjuntos separados. Los matroides gráficos son conexos si y solo si el grafo subyacente es conexo y 2-conexo por vértices . ^{[ 3 ]}

Un matroid es gráfico si y solo si sus menores no incluyen ninguno de los cinco menores prohibidos: el matroid uniforme${\displaystyle U{}_{4}^{2}}$, el plano de Fano o su dual, o los duales de${\displaystyle M(K_{5})}$y${\displaystyle M(K_{3,3})}$definido a partir del gráfico completo${\displaystyle K_{5}}$y el grafo bipartito completo${\displaystyle K_{3,3}}$. ^{[ 3 ] [ 5 ] [ 6 ]} Los tres primeros de estos son los menores prohibidos para los matroides regulares, ^{[ 7 ]} y los duales de${\displaystyle M(K_{5})}$y${\displaystyle M(K_{3,3})}$son regulares pero no gráficas.

Si un matroide es gráfico, su dual (un "matroide cográfico") no puede contener los duales de estos cinco menores prohibidos. Por lo tanto, el dual también debe ser regular y no puede contener como menores los dos matroides gráficos.${\displaystyle M(K_{5})}$y${\displaystyle M(K_{3,3})}$. ^{[ 3 ]}

Debido a esta caracterización y al teorema de Wagner que caracteriza los grafos planares como los grafos sin${\displaystyle K_{5}}$o${\displaystyle K_{3,3}}$gráfico menor , se deduce que un matroid gráfico${\displaystyle M(G)}$es cográfica si y solo si${\displaystyle G}$es planar; este es el criterio de planaridad de Whitney . Si${\displaystyle G}$es planar, el dual de${\displaystyle M(G)}$es el matroide gráfico del grafo dual de${\displaystyle G}$. Mientras${\displaystyle G}$pueden tener múltiples grafos duales, sus matroides gráficos son todos isomorfos. ^{[ 3 ]}

Una base de peso mínimo de un matroide gráfico es un árbol de expansión mínima (o bosque de expansión mínima, si el grafo subyacente es desconectado). Se han estudiado intensamente los algoritmos para calcular árboles de expansión mínima; se sabe cómo resolver el problema en tiempo esperado aleatorio lineal en un modelo de comparación de computación, ^{[ 8 ]} o en tiempo lineal en un modelo de computación en el que los pesos de las aristas son enteros pequeños y se permiten operaciones bit a bit en sus representaciones binarias. ^{[ 9 ]} El límite de tiempo más rápido conocido que se ha demostrado para un algoritmo determinista es ligeramente superlineal. ^{[ 10 ]}

Varios autores han investigado algoritmos para comprobar si un matroide dado es gráfico. ^{[ 11 ] [ 12 ] [ 13 ]} Por ejemplo, un algoritmo de Tutte (1960) resuelve este problema cuando se sabe que la entrada es un matroide binario . Seymour (1981) resuelve este problema para matroides arbitrarios teniendo acceso al matroide solo a través de un oráculo de independencia , una subrutina que determina si un conjunto dado es independiente o no.

Algunas clases de matroides se han definido a partir de familias de grafos bien conocidas, formulando una caracterización de estos grafos en términos que tienen sentido de manera más general para los matroides. Estas incluyen los matroides bipartitos , en los que cada circuito es par, y los matroides eulerianos , que pueden particionarse en circuitos disjuntos. Un matroide gráfico es bipartito si y solo si proviene de un grafo bipartito , y un matroide gráfico es euleriano si y solo si proviene de un grafo euleriano . Dentro de los matroides gráficos (y de forma más general dentro de los matroides binarios ), estas dos clases son duales: un matroide gráfico es bipartito si y solo si su matroide dual es euleriano, y un matroide gráfico es euleriano si y solo si su matroide dual es bipartito. ^{[ 14 ]}

Los matroides gráficos son matroides de rigidez unidimensionales , que describen los grados de libertad de estructuras de vigas rígidas que pueden rotar libremente en los vértices donde se unen. En una dimensión, dicha estructura tiene un número de grados de libertad igual a su número de componentes conexas (el número de vértices menos el rango del matroide) y en dimensiones superiores, el número de grados de libertad de una estructura d- dimensional con n vértices es dn menos el rango del matroide. En los matroides de rigidez bidimensionales, los grafos de Laman desempeñan el papel que los árboles de expansión desempeñan en los matroides gráficos, pero la estructura de los matroides de rigidez en dimensiones mayores que dos no se comprende bien. ^{[ 15 ]}