Matroide gráfico

Matroide con bosques de gráficos como conjuntos independientes

En la teoría matemática de los matroides , un matroide gráfico (también llamado matroide de ciclo o matroide de polígono ) es un matroide cuyos conjuntos independientes son los bosques en un grafo no dirigido finito dado . Los matroides duales de los matroides gráficos se denominan matroides co-gráficos o matroides de enlace . ^[1] Un matroide que es tanto gráfico como co-gráfico a veces se denomina 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 .

Definición

Un matroide puede definirse como una familia de conjuntos finitos (llamados los "conjuntos independientes" del matroide) que está cerrada bajo subconjuntos y que satisface la "propiedad de intercambio": si los conjuntos y son ambos independientes, y es mayor que , entonces hay 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 (quitar 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 conectados, por lo que por el principio del palomar hay un componente de que contiene vértices de dos o más componentes de . A lo largo de cualquier camino en desde un vértice en un componente de a un vértice de otro componente, debe haber una arista con puntos finales en dos componentes, y esta arista puede agregarse a para producir un bosque con más aristas. Por lo tanto, forma los conjuntos independientes de un matroide, llamado el matroide gráfico de o . De manera más general, un matroide se denomina gráfico siempre que sea isomorfo al matroide gráfico de un gráfico, independientemente de si sus elementos son en sí mismos bordes en un gráfico. ^[2] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x\in A\setminus B}$ ${\displaystyle B\cup \{x\}}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle M(G)}$

Las bases de un matroide gráfico son los bosques de expansión completa de , y los circuitos de son los ciclos simples de . El rango en de un conjunto de aristas de un grafo es donde es el número de vértices en el subgrafo formado por las aristas en y es el número de componentes conectados del mismo subgrafo. ^[2] El corank del matroide gráfico se conoce como rango de circuito o número ciclomático. ${\displaystyle M(G)}$ ${\displaystyle G}$ ${\displaystyle M(G)}$ ${\displaystyle G}$ ${\displaystyle M(G)}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle r(X)=n-c}$ ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle c}$

El entramado de pisos

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

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

Representación

El matroide gráfico de un grafo se puede definir como el matroide columna de cualquier matriz de incidencia orientada de . Una matriz de este tipo tiene una fila para cada vértice y una columna para cada arista. La columna para la arista tiene en la fila para un extremo, en la fila para el otro extremo y en otros lugares; la elección de qué extremo dar qué signo es arbitraria. El matroide columna de esta matriz tiene como conjuntos independientes los subconjuntos linealmente independientes de columnas. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle +1}$ ${\displaystyle -1}$ ${\displaystyle 0}$

Si un conjunto de aristas contiene un ciclo, entonces las columnas correspondientes (multiplicadas por si es necesario para reorientar las aristas de manera consistente alrededor del ciclo) suman cero y no son independientes. Por el contrario, si un conjunto de aristas forma un bosque, entonces al eliminar repetidamente las hojas de este bosque se puede demostrar por inducción que el conjunto correspondiente de columnas es independiente. Por lo tanto, la matriz columna es isomorfa a . ${\displaystyle -1}$ ${\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 sobre todos los campos posibles. ^[2]

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

Conectividad Matroid

Se dice que un matroide es conexo si no es la suma directa de dos matroides más pequeñas; 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 en estos subconjuntos separados. Los matroides gráficos son conexos si y solo si el grafo subyacente es conexo y conexo por 2 vértices . ^[2]

Menores y dualidad

Dos grafos diferentes (rojos) que son duales del mismo grafo planar (azul pálido). A pesar de no ser isomorfos como grafos, tienen matroides gráficos isomorfos.

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

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 a los dos matroides gráficos y . ^[2] ${\displaystyle M(K_{5})}$ ${\displaystyle M(K_{3,3})}$

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

Algoritmos

Una base de peso mínimo de un matroide gráfico es un árbol de expansión mínimo (o bosque de expansión mínimo, si el gráfico subyacente está desconectado). Los algoritmos para calcular árboles de expansión mínimos se han estudiado intensamente; se sabe cómo resolver el problema en tiempo esperado aleatorio lineal en un modelo de comparación de cálculo, ^[7] o en tiempo lineal en un modelo de cálculo 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. ^[8] El límite de tiempo más rápido conocido que se ha demostrado para un algoritmo determinista es ligeramente superlineal. ^[9]

Varios autores han investigado algoritmos para probar si un matroide dado es gráfico. ^{[10] [11] [12]} 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 a los que se les da 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.

Clases relacionadas de matroides

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. Estos incluyen los matroides bipartitos , en los que cada circuito es par, y los matroides eulerianos , que pueden dividirse 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 más generalmente 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. ^[13]

Los matroides gráficos son matroides de rigidez unidimensionales , matroides que describen los grados de libertad de estructuras de vigas rígidas que pueden rotar 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 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 desempeñan los árboles de expansión en los matroides gráficos, pero la estructura de los matroides de rigidez en dimensiones mayores que dos no se entiende bien. ^[14]

Referencias

1. Tutte (1965) utiliza una terminología inversa, en la que llama a los matroides de enlace "gráficos" y a los matroides de ciclo "co-gráficos", pero esto no ha sido seguido por autores posteriores.
2. Tutte, WT (1965), "Conferencias sobre matroides" (PDF) , Revista de investigación de la Oficina Nacional de Normas , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781. Véase en particular la sección 2.5, "Matroide de enlace de un grafo", págs. 5-6, la sección 5.6, "Matroides gráficas y cográficas", págs. 19-20, y la sección 9, "Matroides gráficas", págs. 38-47.
3. Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3.ª ed.), American Mathematical Society, pág. 95, ISBN 9780821810255.
4. Seymour, PD (1980), "Sobre la caracterización de Tutte de los matroides gráficos", Annals of Discrete Mathematics , 8 : 83–90, doi :10.1016/S0167-5060(08)70855-0, ISBN 9780444861108, Sr.  0597159.
5. Gerards, AMH (1995), "Sobre la caracterización de Tutte de los matroides gráficos: una prueba gráfica", Journal of Graph Theory , 20 (3): 351–359, doi :10.1002/jgt.3190200311, MR  1355434, S2CID  31334681.
6. Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 (1): 144–174, doi :10.2307/1993244, JSTOR  1993244, MR  0101526.
7. Karger, David R. ; Klein, Philip N.; Tarjan, Robert E. (1995), "Un algoritmo de tiempo lineal aleatorio para encontrar árboles de expansión mínimos", Journal of the Association for Computing Machinery , 42 (2): 321–328, doi : 10.1145/201019.201022 , MR  1409738
8. Fredman, ML ; Willard, DE (1994), "Algoritmos transdicotómicos para árboles de expansión mínima y caminos más cortos", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064-9 , MR  1279413.
9. Chazelle, Bernard (2000), "Un algoritmo de árbol de expansión mínimo con complejidad de tipo Ackermann inverso", Journal of the Association for Computing Machinery , 47 (6): 1028–1047, doi : 10.1145/355541.355562 , MR  1866456, S2CID  6276962.
10. Tutte, WT (1960), "Un algoritmo para determinar si un matroide binario dado es gráfico". Actas de la American Mathematical Society , 11 (6): 905–917, doi :10.2307/2034435, JSTOR  2034435, MR  0117173.
11. Bixby, Robert E.; Cunningham, William H. (1980), "Conversión de programas lineales a problemas de red", Matemáticas de la investigación de operaciones , 5 (3): 321–357, doi :10.1287/moor.5.3.321, MR  0594849.
12. Seymour, PD (1981), "Reconocimiento de matroides gráficos", Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418, S2CID  35579707.
13. Welsh, DJA (1969), "Matroides de Euler y bipartitos", Journal of Combinatorial Theory , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR  0237368.
14. Whiteley, Walter (1996), "Algunas matroides de geometría aplicada discreta", Matroid theory (Seattle, WA, 1995) , Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, págs. 171–311, doi : 10.1090/conm/197/02540 , ISBN 978-0-8218-0508-4, Sr.  1411692.