En la teoría matemática de las matroides , una matroide gráfica (también llamada matroide cíclica 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 tanto gráfica como co-gráfica se llama matroide plana ; 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": if sets y son independientes y Es mas grande que , entonces hay un elemento tal que permanece independiente. Si es un gráfico no dirigido, y es la familia de conjuntos de bordes que forman bosques en , luego está claramente cerrado bajo subconjuntos (eliminar los bordes 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 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 se puede agregar a para producir un bosque con más bordes. Por lo tanto, forma los conjuntos independientes de un matroide, llamado el matroide gráfico de o . De manera más general, una matroide se denomina gráfica siempre que sea isomórfica a la matroide gráfica de un gráfico, independientemente de si sus elementos son en sí mismos bordes en un gráfico. [2]
Las bases de una matroide gráfica son los bosques que se extienden por completo de, y los circuitos de son los ciclos simples de. El rango en de un conjunto de aristas de una gráfica es dónde es el número de vértices en el subgrafo formado por los bordes en y es el número de componentes conectados del mismo subgrafo. [2] La corank de la matroide gráfica se conoce como rango de circuito o número ciclomático.
La celosía de los pisos
El cierre de un conjunto de bordes en es un plano que consta de los bordes que no son independientes de (es decir, los bordes cuyos extremos están conectados entre sí por una ruta en ). Este piso puede identificarse con la partición de los vértices deen los componentes conectados del subgrafo formado por: Cada conjunto de bordes tiene el mismo cierre que da lugar a la misma partición de los vértices, y puede recuperarse de la partición de los vértices, ya que consta de los bordes cuyos extremos pertenecen al mismo conjunto en la partición. En la celosía de pisos de esta matroide, hay una relación de orden siempre que la partición correspondiente a plano es un refinamiento de la partición correspondiente a plano .
En este aspecto de las matroides gráficas, la matroide gráfica para un gráfico completo es particularmente importante, porque permite que todas las particiones posibles del conjunto de vértices se formen como el conjunto de componentes conectados de algún subgrafo. Así, la celosía de pisos de la matroide gráfica dees naturalmente isomorfo a la celosía de las particiones de un-conjunto de elementos . Dado que las celosías de los planos de matroides son exactamente las celosías geométricas , esto implica que la celosía de las particiones también es geométrica. [3]
Representación
La matroide gráfica de un gráfico puede definirse como la columna matroide de cualquier matriz de incidencia orientada de. Tal matriz tiene una fila para cada vértice y una columna para cada borde. La columna de borde posee en la fila para un punto final, en la fila para el otro punto final, y en otra parte; la elección de qué punto final dar qué signo es arbitraria. La matriz de columnas de esta matriz tiene como conjuntos independientes los subconjuntos de columnas linealmente independientes.
Si un conjunto de aristas contiene un ciclo, entonces las columnas correspondientes (multiplicadas por si es necesario para reorientar los bordes consistentemente alrededor del ciclo) suma cero y no es independiente. Por el contrario, si un conjunto de bordes forma un bosque, al quitar repetidamente las hojas de este bosque se puede demostrar por inducción que el conjunto de columnas correspondiente es independiente. Por lo tanto, la matriz de la columna es isomorfa a.
Este método de representar 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]
La celosía de planos de una matroide gráfica también se puede realizar como la celosía de una disposición de hiperplano , de hecho, como un subconjunto de la disposición de trenza , cuyos hiperplanos son las diagonales.. Es decir, si los vértices de están incluimos el hiperplano cuando sea es un borde de .
Conectividad Matroid
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 de modo 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 por 2 vértices . [2]
Menores y dualidad
Un matroid es gráfico si y solo si sus menores no incluyen a ninguno de los cinco menores prohibidos: el matroid uniforme , el plano de Fano o su dual, o los duales de y definido a partir del gráfico completo y el gráfico bipartito completo . [2] [4] [5] Los tres primeros son los menores prohibidos para los matroids regulares, [6] y los duales de y son regulares pero no gráficos.
Si un matroid es gráfico, su dual (un "matroid co-gráfico") no puede contener los duales de estos cinco menores prohibidos. Así, el dual también debe ser regular, y no puede contener como menores las dos matroides gráficas y . [2]
Debido a esta caracterización y al teorema de Wagner que caracteriza las gráficas planas como gráficas sin o grafica menor , se deduce que una matroide gráfica es cográfico si y solo si es plano; este es el criterio de planitud de Whitney . Si es plano, el dual de es la matroide gráfica del gráfico dual de. Tiempopueden tener múltiples gráficos duales, sus matroides gráficos son todos isomorfos. [2]
Algoritmos
Una base de peso mínimo de una matriz 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). Los algoritmos para calcular árboles de expansión mínimos se han estudiado intensamente; se sabe cómo resolver el problema en tiempo esperado lineal aleatorio 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 pequeños enteros 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 probado para un algoritmo determinista es ligeramente superlineal. [9]
Varios autores han investigado algoritmos para probar si una determinada matriz es gráfica. [10] [11] [12] Por ejemplo, un algoritmo de Tutte (1960) resuelve este problema cuando se sabe que la entrada es una matriz binaria . Seymour (1981) resuelve este problema para matroides arbitrarios a los que se les da acceso a la 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 conocidas de gráficos, formulando una caracterización de estos gráficos en términos que tienen sentido de manera más general para los matroides. Estos incluyen las matroides bipartitas , en las que todos los circuitos son pares, y las matroides eulerianas , que pueden dividirse en circuitos disjuntos. Un matroide gráfico es bipartito si y solo si proviene de un gráfico bipartito y un matroide gráfico es euleriano si y solo si proviene de un gráfico 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 en expansión en las matroides gráficas, pero la estructura de las matroides de rigidez en dimensiones superiores a dos no se comprende bien. [14]
Referencias
- ↑ Tutte (1965) usa una terminología inversa, en la que llamó a las matroides de enlace "gráficas" y a las matroides cíclicas "co-gráficas", pero esto no ha sido seguido por autores posteriores.
- ^ a b c d e f g 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 , Señor 0179781. Véase en particular la sección 2.5, "Bond-matroid de un gráfico", págs. 5-6, la sección 5.6, "Gráficas y co-gráficas matroides", págs. 19-20, y la sección 9, "Gráficas matroides", págs. 38–47.
- ^ Birkhoff, Garrett (1995), Lattice Theory , Colloquium Publications, 25 (3ª ed.), American Mathematical Society, p. 95, ISBN 9780821810255 CS1 maint: parámetro desalentado ( enlace ).
- ^ Seymour, PD (1980), "Sobre la caracterización de Tutte de las matroides gráficas", Annals of Discrete Mathematics , 8 : 83–90, doi : 10.1016 / S0167-5060 (08) 70855-0 , MR 0597159 CS1 maint: parámetro desalentado ( enlace ).
- ^ Gerards, AMH (1995), "Sobre la caracterización de matroides gráficos de Tutte: una prueba gráfica", Journal of Graph Theory , 20 (3): 351–359, doi : 10.1002 / jgt.3190200311 , MR 1355434.
- ^ Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 : 144-174, doi : 10.2307 / 1993244 , MR 0101526 CS1 maint: parámetro desalentado ( enlace ).
- ^ 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
- ^ Fredman, ML ; Willard, DE (1994), "Algoritmos trans-dicotómicos para árboles de expansión mínimos 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.
- ^ 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 CS1 maint: parámetro desalentado ( enlace ).
- ^ Tutte, WT (1960), "Un algoritmo para determinar si una determinada matriz binaria es gráfica", Proceedings of the American Mathematical Society , 11 : 905–917, doi : 10.2307 / 2034435 , MR 0117173 CS1 maint: parámetro desalentado ( enlace ).
- ^ Bixby, Robert E .; Cunningham, William H. (1980), "Conversión de programas lineales en problemas de red", Mathematics of Operations Research , 5 (3): 321–357, doi : 10.1287 / moor.5.3.321 , MR 0594849.
- ^ Seymour, PD (1981), "Recognizing graphic matroids", Combinatorica , 1 (1): 75–78, doi : 10.1007 / BF02579179 , MR 0602418 CS1 maint: parámetro desalentado ( enlace ).
- ^ Welsh, DJA (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory , 6 : 375–377, doi : 10.1016 / s0021-9800 (69) 80033-5 , MR 0237368 CS1 maint: parámetro desalentado ( enlace ).
- ^ Whiteley, Walter (1996), "Algunas matroides de la geometría aplicada discreta", Teoría Matroide (Seattle, WA, 1995) , Matemáticas contemporáneas, 197 , Providence, RI: American Mathematical Society, págs. 171–311, doi : 10.1090 / conm / 197/02540 , MR 1411692 CS1 maint: parámetro desalentado ( enlace ).