Matroide gráfica

Matroide con bosques de gráficos como conjuntos independientes

En la teoría matemática de 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 cográficas o matroides de enlace . ^[1] 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

Una matroide puede definirse como una familia de conjuntos finitos (llamados "conjuntos independientes" de la matroide) que está cerrada bajo subconjuntos y que satisface la "propiedad de intercambio": si los conjuntos y son ambos independientes y son mayores que , entonces hay 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 conectados, por lo que según el principio de 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 un borde con puntos finales en dos componentes, y este borde se puede agregar para producir un bosque con más bordes. Así, se forman los conjuntos independientes de una matroide, llamados matroide gráfica de o . De manera más general, una matroide se llama gráfica siempre que sea isomorfa a la matroide gráfica 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 completos de , y los circuitos de son los ciclos simples de . El rango de un conjunto de aristas de un gráfico es donde está el número de vértices en el subgrafo formado por las aristas y es el número de componentes conectados del mismo subgrafo. ^[2] El corank de la matroide gráfica 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 consta de aristas que no son independientes de (es decir, las aristas cuyos puntos finales están conectados entre sí por una ruta en ). Este plano puede identificarse con la partición de los vértices de en los componentes conectados del subgrafo formado por : Cada conjunto de aristas que tienen el mismo cierre que da lugar a la misma partición de los vértices, y pueden recuperarse de la partición del vértices, ya que consta de aristas cuyos puntos finales pertenecen al mismo conjunto en la partición. En el entramado de pisos de esta matroide, existe 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 las matroides gráficas, la matroide gráfica para un gráfico completo es particularmente importante, porque permite que cada partición posible del conjunto de vértices se forme como el conjunto de componentes conectados de algún subgrafo. Por lo tanto, la red de pisos de la matroide gráfica de es naturalmente isomorfa a la red de particiones de un conjunto de elementos . Dado que las celosías de los pisos de las matroides son exactamente las celosías geométricas , esto implica que la celosía de las particiones también es geométrica. ^[3] ${\displaystyle K_{n}}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$

Representación

La matroide gráfica de un gráfico se puede definir como la matroide de columna de cualquier matriz de incidencia orientada de . Dicha matriz tiene una fila para cada vértice y una columna para cada arista. La columna de borde tiene en la fila un punto final, en la fila el otro punto final y en otros lugares; la elección de qué punto final dar qué signo es arbitraria. La matroide de columnas de esta matriz tiene como conjuntos independientes los subconjuntos de columnas linealmente independientes. ${\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 consistentemente alrededor del ciclo) suman cero y no son independientes. Por el contrario, si un conjunto de aristas forma un bosque, eliminando 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 la 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 en todos los campos posibles. ^[2]

El entramado de planos de una matroide gráfica también se puede realizar como el entramado de una disposición de hiperplano , de hecho como un subconjunto de la disposición trenzada , 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 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 . ^[2]

Menores y dualidad

Dos gráficos diferentes (rojo) que son duales del mismo gráfico plano (azul pálido). A pesar de no ser isomorfos como gráficos, tienen matroides gráficas isomorfas.

Una matroide es gráfica si y sólo si sus menores no incluyen ninguno de los cinco menores prohibidos: la 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 son los menores prohibidos para las 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 una matroide es gráfica, su dual (una "matroide cográfica") 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 y . ^[2] ${\displaystyle M(K_{5})}$ ${\displaystyle M(K_{3,3})}$

Debido a esta caracterización y al teorema de Wagner que caracteriza las gráficas planas como gráficas sin grafo menor o sin grafo , se deduce que una matroide gráfica es cográfica si y solo si es plana; este es el criterio de planaridad de Whitney . Si es plano, el dual de es la matroide gráfica del gráfico dual de . Si bien pueden tener múltiples gráficos duales, sus matroides gráficas son todas isomorfas. ^[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 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, ^[7] 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. ^[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 una matroide determinada es gráfica. ^{[10] [11] [12]} 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 les 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. ^[13]

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 una estructura d -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. ^[14]

Referencias

1. Tutte (1965) utiliza una terminología invertida, en la que llamó a las matroides de enlace "gráficas" y a las matroides de ciclo "cográficas", 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 Estándares , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781. Consulte en particular la sección 2.5, "Matroide de enlace de un gráfico", 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), Teoría del entramado, Publicaciones del coloquio, vol. 25 (3ª ed.), Sociedad Matemática Estadounidense, pág. 95, ISBN 9780821810255.
4. Seymour, PD (1980), "Sobre la caracterización de matroides gráficas de Tutte", Annals of Discrete Mathematics , 8 : 83–90, doi :10.1016/S0167-5060(08)70855-0, ISBN 9780444861108, señor  0597159.
5. Gerards, AMH (1995), "Sobre la caracterización de Tutte de las matroides gráficas: 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 aleatorio de tiempo lineal para encontrar árboles de expansión mínima", Revista de la Asociación de Maquinaria de Computación , 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 , señor  1279413.
9. Chazelle, Bernard (2000), "Un algoritmo de árbol de expansión mínimo con complejidad de tipo Ackermann inverso", Revista de la Asociación de Maquinaria de Computación , 47 (6): 1028–1047, doi : 10.1145/355541.355562 , MR  1866456, S2CID  6276962.
10. Tutte , WT ( 1960 ), " Un algoritmo  para determinar si una matroide binaria determinada  es gráfica " ..
11. Bixby, Robert E.; Cunningham, William H. (1980), "Conversión de programas lineales en problemas de red", Matemáticas de la investigación de operaciones , 5 (3): 321–357, doi :10.1287/moor.5.3.321, SEÑOR  0594849.
12. Seymour, PD (1981), "Reconocimiento de matroides gráficas", Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418, S2CID  35579707.
13. Welsh, DJA (1969), "Euler y las matroides bipartitas", 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", Teoría de matroides (Seattle, WA, 1995) , Contemporary Mathematics, vol. 197, Providence, RI: Sociedad Matemática Estadounidense, págs. 171–311, doi : 10.1090/conm/197/02540 , SEÑOR  1411692.