Matroide 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 gráfico finito no dirigido dado. Las matroides duales de las matroides gráficas se denominan matroides co-gráficas o matroides de enlace. Una matroide que es a la vez gráfica y cográfica a veces se denomina matroide plana (pero esto no debe confundirse con las matroides de rango 3, que generalizan configuraciones de puntos planos); estas son exactamente las matroides gráficas formadas a partir de gráficos planos.

Definición

Un matroide puede definirse como una familia de conjuntos finitos (llamados los "grupos independientes" del matroide) que se cierra bajo subconjuntos y que satisface la "propiedad de cambio": si se pone ${displaystyle A}$ y ${displaystyle B}$ son independientes, y ${displaystyle A}$ es más grande que ${displaystyle B}$, entonces hay un elemento ${displaystyle xin Asetminus B}$ tales que ${displaystyle Bcup {x}$ sigue siendo independiente. Si ${displaystyle G.$ es un gráfico no dirigido, y ${displaystyle F}$ es la familia de conjuntos de bordes que forman bosques en ${displaystyle G.$Entonces ${displaystyle F}$ está claramente cerrado bajo subconjuntos (removiendo bordes de un bosque deja otro bosque). También satisface la propiedad de cambio: si ${displaystyle A}$ y ${displaystyle B}$ ambos bosques, y ${displaystyle A}$ tiene más bordes que ${displaystyle B}$, entonces tiene menos componentes conectados, por lo que por el principio de la paloma hay un componente ${displaystyle C}$ de ${displaystyle A}$ que contiene vértices de dos o más componentes ${displaystyle B}$. Por cualquier camino ${displaystyle C}$ de un vértice en un componente ${displaystyle B}$ a un vértice de otro componente, debe haber un borde con puntos finales en dos componentes, y este borde puede ser añadido a ${displaystyle B}$ para producir un bosque con más bordes. Así, ${displaystyle F}$ forma los conjuntos independientes de un materoide, llamado el materoide gráfico ${displaystyle G.$ o ${displaystyle M(G)}$. Más generalmente, un materoide se llama gráfico cuando es isomorfo al materoide gráfico de un gráfico, independientemente de si sus elementos son en sí mismos bordes en un gráfico.

Las bases de un materoide gráfico ${displaystyle M(G)}$ son los bosques llenos de ${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 bordes de un gráfico ${displaystyle G.$ es ${displaystyle r(X)=n-c}$ Donde ${displaystyle n}$ es el número de vértices en el subgrafo formado por los bordes en ${displaystyle X}$ y ${displaystyle c}$ es el número de componentes conectados del mismo subgrafo. El corank del materoide gráfico se conoce como el rango de circuito o número ciclomático.

La celosía de los pisos

El cierre ${displaystyle operatorname {cl} (S)}$ de un conjunto ${displaystyle S.$ de bordes en ${displaystyle M(G)}$ es un piso que consiste en los bordes que no son independientes de ${displaystyle S.$ (es decir, los bordes cuyos puntos finales están conectados entre sí por un camino en ${displaystyle S.$). Este piso se puede identificar con la partición de los vértices ${displaystyle G.$ en los componentes conectados del subgrafo formado por ${displaystyle S.$: Cada conjunto de bordes con el mismo cierre que ${displaystyle S.$ da lugar a la misma partición de los vértices, y ${displaystyle operatorname {cl} (S)}$ se puede recuperar de la partición de los vértices, ya que consta de los bordes cuyos puntos finales pertenecen al mismo conjunto en la partición. En la celosía de los planos de este materoide, hay una relación de orden ${displaystyle xleq y}$ cuando la partición correspondiente al plano${displaystyle x}$ es un refinamiento de la partición correspondiente al plano${displaystyle y}$.

En este aspecto de los materoides gráficos, el materoide gráfico para un gráfico completo ${displaystyle K_{n}$ es particularmente importante, ya que permite que cada partición posible del vértice se forme como el conjunto de componentes conectados de algún subgraph. Así, la celosía de los planos del materoide gráfico de ${displaystyle K_{n}$ es naturalmente isomorfo para lattice de particiones de un ${displaystyle n}$-Element set. Dado que las celosías de los planos de los materoides son exactamente las rejillas geométricas, esto implica que la celosía de las particiones es también geométrica.

Representación

El materoide gráfico de un gráfico ${displaystyle G.$ se puede definir como el matroide de columna de cualquier matriz de incidencia orientada ${displaystyle G.$. Tal matriz tiene una fila para cada vértice, y una columna para cada borde. La columna para el borde ${displaystyle e}$ tiene ${displaystyle +1}$ en la fila por un punto final, ${displaystyle -1}$ en la fila por el otro punto final, y ${displaystyle 0}$ en otros lugares; la elección del punto final para dar qué signo es arbitrario. La columna matroid de esta matriz tiene como su independiente establece los subconjuntos linealmente independientes de las columnas.

Si un conjunto de bordes contiene un ciclo, entonces las columnas correspondientes (multiplicadas por ${displaystyle -1}$ si es necesario reorientar los bordes constantemente alrededor del ciclo) suma a cero, y no es independiente. Por el contrario, si un conjunto de bordes forma un bosque, entonces al retirar 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 columna es isomorfa a ${displaystyle M(G)}$.

Este método de representación de matroides gráficas funciona independientemente del campo sobre el que se define la incidencia. Por lo tanto, las matroides gráficas forman un subconjunto de las matroides regulares, matroides que tienen representaciones en todos los campos posibles.

La celosía de los planos de un materoide gráfico también se puede realizar como la celosía de un arreglo hiperplano, de hecho como un subconjunto del arreglo trenzado, cuyos hiperplanos son las diagonales ${displaystyle H_{ij}={(x_{1},ldotsx_{n}in mathbb {R} {n}mid} #$. Es decir, si los vértices de ${displaystyle G.$ son ${displaystyle v_{1},ldotsv_{n}$ incluimos el hiperplano ${displaystyle H_{ij}$ siempre ${displaystyle E=v_{i}v_{j}}$ es un borde de ${displaystyle G.$.

Conectividad matroide

Se dice que una matroide está conectada si no es la suma directa de dos matroides más pequeñas; es decir, está conectado si y sólo si no existen dos subconjuntos disjuntos de elementos tales que la función de rango de la matroide sea igual a la suma de los rangos en estos subconjuntos separados. Las matroides gráficas están conectadas si y solo si el gráfico subyacente está conectado y conectado con 2 vértices.

Los menores y la dualidad

Un matroide es gráfico si y sólo si sus menores no incluyen a ninguno de los cinco menores prohibidos: el materoide uniforme ${displaystyle ¿Qué?$, el plano Fano o su dual, o los duales de ${displaystyle M(K_{5}}$ y ${displaystyle M(K_{3,3})}$ definido en el gráfico completo ${displaystyle K_{5}$ y el gráfico bipartito completo ${displaystyle K_{3,3}}$. Los tres primeros son los menores prohibidos para los esteroides regulares, y los duales de ${displaystyle M(K_{5}}$ y ${displaystyle M(K_{3,3})}$ son regulares pero no gráficos.

Si un matroide es gráfico, su dual (un "matroide cográfico") no puede contener las dobles de estos cinco menores prohibidos. Así, el dual debe ser también regular, y no puede contener como menores los dos materoides gráficos ${displaystyle M(K_{5}}$ y ${displaystyle M(K_{3,3})}$.

Debido a esta caracterización y el teorema de Wagner caracterizando los gráficos planares como los gráficos sin ${displaystyle K_{5}$ o ${displaystyle K_{3,3}}$ gráfico menor, sigue que un materoide gráfico ${displaystyle M(G)}$ es co-gráfico si y sólo si ${displaystyle G.$ es planar; este es el criterio de la planaridad de Whitney. Si ${displaystyle G.$ es planar, el doble de ${displaystyle M(G)}$ es el materoide gráfico del gráfico dual ${displaystyle G.$. Mientras tanto ${displaystyle G.$ puede tener múltiples gráficos duales, sus materoides gráficos son todo isomorfo.

Algoritmos

Una base de peso mínimo de una matroide gráfica es un árbol de expansión mínimo (o un bosque de expansión mínimo, si el gráfico subyacente está 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 lineal aleatorio en un modelo de computación de comparación, o en tiempo lineal en un modelo de computación en el que los pesos de los bordes son números enteros pequeños y se permiten operaciones bit a bit en sus representaciones binarias. El límite de tiempo más rápido conocido que se ha demostrado para un algoritmo determinista es ligeramente superlineal.

Varios autores han investigado algoritmos para probar si una matroide determinada es gráfica. Por ejemplo, un algoritmo de Tutte (1960) resuelve este problema cuando se sabe que la entrada es una matroide binaria. Seymour (1981) resuelve este problema para matroides arbitrarias a las que se da acceso a la matroide sólo a través de un oráculo de independencia, una subrutina que determina si un conjunto dado es independiente o no.

Clases relacionadas de matroides

Algunas clases de matroides se han definido a partir de familias de gráficos bien conocidas, formulando una caracterización de estos gráficos en términos que tengan sentido de manera más general para matroides. Estos incluyen las matroides bipartitas, en las que cada circuito es par, y las matroides eulerianas, que pueden dividirse en circuitos disjuntos. Una matroide gráfica es bipartita si y sólo si proviene de un grafo bipartito y una matroide gráfica es euleriana si y sólo si proviene de un grafo euleriano. Dentro de las matroides gráficas (y más generalmente dentro de las matroides binarias) estas dos clases son duales: una matroide gráfica es bipartita si y solo si su matroide dual es euleriana, y una matroide gráfica es euleriana si y solo si su matroide dual es bipartita.

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