En teoría de grafos , un gráfico no dirigido H se llama menor del gráfico G si H puede formarse a partir de G eliminando aristas, vértices y contrayendo aristas .
La teoría de los grafos menores comenzó con el teorema de Wagner de que un grafo es plano si y sólo si sus menores no incluyen ni el grafo completo K 5 ni el grafo bipartito completo K 3,3 . [1] El teorema de Robertson-Seymour implica que existe una caracterización menor prohibida análoga para cada propiedad de los gráficos que se conserva mediante eliminaciones y contracciones de bordes. [2] Para cada gráfico fijo H , es posible probar si H es menor de un gráfico de entrada G en tiempo polinómico ; [3] junto con la caracterización menor prohibida, esto implica que cada propiedad del gráfico preservada por eliminaciones y contracciones puede reconocerse en tiempo polinómico. [4]
Otros resultados y conjeturas que involucran gráficos menores incluyen el teorema de la estructura del gráfico , según el cual los gráficos que no tienen H como menor pueden formarse pegando piezas más simples, y la conjetura de Hadwiger que relaciona la incapacidad de colorear un gráfico con la existencia de un gráfico completo grande como menor del mismo. Las variantes importantes de gráficos menores incluyen los menores topológicos y los menores de inmersión.
Una contracción de arista es una operación que elimina una arista de un gráfico y al mismo tiempo fusiona los dos vértices que solía conectar. Un gráfico no dirigido H es menor de otro gráfico no dirigido G si se puede obtener un gráfico isomorfo a H a partir de G contrayendo algunas aristas, eliminando algunas aristas y eliminando algunos vértices aislados. El orden en el que se realiza una secuencia de tales contracciones y eliminaciones en G no afecta el gráfico resultante H.
Los menores gráficos a menudo se estudian en el contexto más general de los menores matroides . En este contexto, es común suponer que todos los gráficos están conectados, con bucles automáticos y aristas múltiples permitidas (es decir, son multigrafos en lugar de gráficos simples); la contracción de un bucle y la eliminación de un borde de corte son operaciones prohibidas. Este punto de vista tiene la ventaja de que las eliminaciones de bordes dejan el rango de un gráfico sin cambios y las contracciones de bordes siempre reducen el rango en uno.
En otros contextos (como en el estudio de pseudobosques ) tiene más sentido permitir la eliminación de un borde de corte y permitir gráficos desconectados, pero prohibir los multigrafos. En esta variación de la teoría de grafos menores, un gráfico siempre se simplifica después de cualquier contracción de aristas para eliminar sus bucles automáticos y aristas múltiples. [5]
Una función f se denomina "monótona menor" si, siempre que H es menor de G , se tiene f ( H ) ≤ f ( G ) .
En el siguiente ejemplo, el gráfico H es menor del gráfico G :
h.
GRAMO.
El siguiente diagrama ilustra esto. Primero construya un subgrafo de G eliminando los bordes discontinuos (y el vértice aislado resultante), y luego contraiga el borde gris (fusionando los dos vértices que conecta):
Es sencillo verificar que la relación menor del grafo forma un orden parcial en las clases de isomorfismo de grafos finitos no dirigidos: es transitiva (un menor de un menor de G es menor de G mismo), y G y H solo pueden ser menores. entre sí si son isomórficos porque cualquier operación menor no trivial elimina aristas o vértices. Un resultado profundo de Neil Robertson y Paul Seymour afirma que este orden parcial es en realidad un cuasiordenamiento : si se da una lista infinita ( G 1 , G 2 ,…) de gráficos finitos, entonces siempre existen dos índices i < j tal que G i es menor de G j . Otra forma equivalente de decir esto es que cualquier conjunto de gráficos sólo puede tener un número finito de elementos mínimos bajo el orden menor. [6] Este resultado demostró una conjetura anteriormente conocida como conjetura de Wagner, en honor a Klaus Wagner ; Wagner lo había conjeturado mucho antes, pero no lo publicó hasta 1970. [7]
En el curso de su demostración, Seymour y Robertson también prueban el teorema de la estructura del grafo en el que determinan, para cualquier gráfico fijo H , la estructura aproximada de cualquier gráfico que no tenga H como menor. El enunciado del teorema es largo y complicado en sí mismo, pero en resumen establece que dicho grafo debe tener la estructura de una suma camarilla de grafos más pequeños que se modifican en pequeñas formas a partir de grafos incrustados en superficies de género acotado . Por tanto, su teoría establece conexiones fundamentales entre grafos menores y incrustaciones topológicas de grafos. [8]
Para cualquier gráfico H , los gráficos simples H sin menores deben ser escasos , lo que significa que el número de aristas es menor que algún múltiplo constante del número de vértices. [9] Más específicamente, si H tiene h vértices, entonces un gráfico simple H sin menores de n vértices puede tener como máximo aristas, y algunos gráficos K h sin menores tienen al menos esta cantidad de aristas. [10] Por lo tanto, si H tiene h vértices, entonces H -los gráficos libres menores tienen grado promedio y, además, degeneración . Además, los H -gráficos libres menores tienen un teorema de separación similar al teorema del separador plano para gráficos planos: para cualquier H fijo y cualquier n -vértice H -gráfico libre menor G , es posible encontrar un subconjunto de vértices cuya eliminación divide G en dos subgrafos (posiblemente desconectados) con como máximo 2 norte ⁄ 3 vértices por subgrafo. [11] Aún más fuerte, para cualquier H fijo , los gráficos libres de H -menor tienen ancho de árbol . [12]
La conjetura de Hadwiger en teoría de grafos propone que si un gráfico G no contiene un isomorfo menor al gráfico completo en k vértices, entonces G tiene una coloración adecuada con k - 1 colores. [13] El caso k = 5 es una reformulación del teorema de los cuatro colores . La conjetura de Hadwiger ha sido probada para k ≤ 6 , [14] pero se desconoce en el caso general. Bollobás, Catlin y Erdős (1980) lo llaman "uno de los problemas sin resolver más profundos de la teoría de grafos". Otro resultado que relaciona el teorema de los cuatro colores con los grafos menores es el teorema de snark anunciado por Robertson, Sanders, Seymour y Thomas, un fortalecimiento del teorema de los cuatro colores conjeturado por WT Tutte y que establece que cualquier grafo de 3 regulares sin puente que requiera cuatro Los colores en una coloración de borde deben tener el gráfico de Petersen como menor. [15]
Muchas familias de grafos tienen la propiedad de que cada menor de un grafo en F también está en F ; Se dice que dicha clase es menor-cerrada . Por ejemplo, en cualquier gráfico plano , o cualquier incrustación de un gráfico en una superficie topológica fija , ni la eliminación de aristas ni la contracción de aristas pueden aumentar el género de la incrustación; por lo tanto, los gráficos planos y los gráficos incrustables en cualquier superficie fija forman familias cerradas menores.
Si F es una familia cerrada menor, entonces (debido a la propiedad de cuasi ordenamiento de los menores) entre los gráficos que no pertenecen a F hay un conjunto finito X de gráficos menores-mínimos. Estos grafos son menores prohibidos para F : un grafo pertenece a F si y sólo si no contiene como menor ningún grafo en X. Es decir, cada familia cerrada de menores F puede caracterizarse como la familia de X -gráficos libres de menores para algún conjunto finito X de menores prohibidos. [2] El ejemplo más conocido de una caracterización de este tipo es el teorema de Wagner que caracteriza a los grafos planos como aquellos que no tienen ni K 5 ni K 3,3 como menores. [1]
En algunos casos, las propiedades de los condes de una familia cerrada de menores pueden estar estrechamente relacionadas con las propiedades de sus menores excluidos. Por ejemplo, una familia de gráficos menores cerrados F tiene un ancho de ruta limitado si y solo si sus menores prohibidos incluyen un bosque , [16] F tiene una profundidad de árbol limitada si y solo si sus menores prohibidos incluyen una unión disjunta de gráficos de ruta , F tiene un ancho de ruta limitado ancho de árbol si y solo si sus menores prohibidos incluyen un gráfico plano , [17] y F tiene un ancho de árbol local acotado (una relación funcional entre el diámetro y el ancho del árbol) si y solo si sus menores prohibidos incluyen un gráfico de vértice (un gráfico que puede hacerse plano por la eliminación de un solo vértice). [18] Si H se puede dibujar en el plano con un solo cruce (es decir, tiene el cruce número uno), entonces los gráficos libres de H -menores tienen un teorema de estructura simplificado en el que se forman como sumas de camarillas de planos. gráficos y gráficos de ancho de árbol acotado. [19] Por ejemplo, tanto K 5 como K 3,3 tienen el cruce número uno, y como Wagner demostró, los gráficos libres de K 5 son exactamente las sumas de 3 clics de los gráficos planos y el gráfico de Wagner de ocho vértices , mientras que el Los gráficos libres de K 3,3 son exactamente las sumas de 2 clics de los gráficos planos y K 5 . [20]
Un gráfico H se llama topológico menor de un gráfico G si una subdivisión de H es isomorfa a un subgrafo de G. [21] Todo menor topológico es también menor. Sin embargo, lo contrario no es cierto en general (por ejemplo, el gráfico completo K 5 en el gráfico de Petersen es menor pero no topológico), pero es válido para un gráfico con un grado máximo no mayor que tres. [22]
La relación topológica menor no es un cuasiordenamiento adecuado en el conjunto de gráficos finitos [23] y, por tanto, el resultado de Robertson y Seymour no se aplica a los menores topológicos. Sin embargo, es sencillo construir caracterizaciones topológicas menores finitas prohibidas a partir de caracterizaciones menores finitas prohibidas reemplazando cada conjunto de ramas con k bordes salientes por cada árbol en k hojas que tenga un grado inferior de al menos dos.
Un gráfico H se llama menor inducido de un gráfico G si se puede obtener a partir de un subgrafo inducido de G contrayendo aristas. De lo contrario, se dice que G es libre de menores inducido por H. [24]
Una operación gráfica llamada elevación es central en un concepto llamado inmersiones . El levantamiento es una operación en bordes adyacentes. Dados tres vértices v , u y w , donde (v,u) y (u,w) son aristas en el gráfico, el levantamiento de vuw , o equivalente de (v,u), (u,w) es la operación que elimina los dos bordes (v,u) y (u,w) y agrega el borde (v,w) . En el caso en que (v,w) ya estaba presente, v y w ahora estarán conectados por más de un borde y, por lo tanto, esta operación es intrínsecamente una operación de múltiples gráficos.
En el caso en el que se puede obtener un gráfico H a partir de un gráfico G mediante una secuencia de operaciones de elevación (en G ) y luego encontrando un subgrafo isomórfico, decimos que H es una inmersión menor de G. Existe aún otra forma de definir los menores de inmersión, que equivale a la operación de elevación. Decimos que H es una inmersión menor de G si existe un mapeo inyectivo desde los vértices en H a los vértices en G donde las imágenes de elementos adyacentes de H están conectados en G por caminos de borde disjunto.
La relación de inmersión menor es un cuasi ordenamiento en el conjunto de gráficos finitos y, por tanto, el resultado de Robertson y Seymour se aplica a los menores de inmersión. Esto significa además que toda familia cerrada de menores de inmersión se caracteriza por una familia finita de menores de inmersión prohibidos.
En el dibujo de grafos , los menores de inmersión surgen como las planarizaciones de grafos no planos : a partir del dibujo de un grafo en el plano, con cruces, se puede formar un menor de inmersión reemplazando cada punto de cruce por un nuevo vértice, y en el proceso también subdividiendo cada borde cruzado en un camino. Esto permite que los métodos de dibujo para gráficos planos se extiendan a gráficos no planos. [25]
Un menor poco profundo de un gráfico G es un menor en el que los bordes de G que se contrajeron para formar el menor forman una colección de subgrafos disjuntos con diámetro bajo . Los menores poco profundos interpolan entre las teorías de grafos menores y subgrafos, en el sentido de que los menores poco profundos con gran profundidad coinciden con el tipo habitual de grafos menores, mientras que los menores poco profundos con profundidad cero son exactamente los subgrafos. [26] También permiten que la teoría de grafos menores se extienda a clases de grafos como los grafos uniplanares que no están cerrados en menores. [27]
Una definición alternativa y equivalente de un gráfico menor es que H es menor de G siempre que los vértices de H puedan representarse mediante una colección de subárboles disjuntos de vértices de G , de modo que si dos vértices son adyacentes en H , existe una arista con sus puntos finales en los dos árboles correspondientes en G . Un menor impar restringe esta definición agregando condiciones de paridad a estos subárboles. Si H está representado por una colección de subárboles de G como arriba, entonces H es un menor impar de G siempre que sea posible asignar dos colores a los vértices de G de tal manera que cada borde de G dentro de un subárbol esté correctamente coloreado. (sus puntos finales tienen colores diferentes) y cada borde de G que representa una adyacencia entre dos subárboles es monocromático (sus dos puntos finales son del mismo color). A diferencia del tipo habitual de gráficos menores, los gráficos con menores impares prohibidos no son necesariamente escasos. [28] La conjetura de Hadwiger , de que k -gráficos cromáticos necesariamente contienen k -gráficos completos de vértices como menores, también se ha estudiado desde el punto de vista de los menores impares. [29]
Una extensión diferente basada en la paridad de la noción de gráficos menores es el concepto de menor bipartito, que produce un gráfico bipartito siempre que el gráfico inicial sea bipartito. Un gráfico H es un menor bipartito de otro gráfico G siempre que H pueda obtenerse de G eliminando vértices, eliminando aristas y colapsando pares de vértices que están a una distancia de dos entre sí a lo largo de un ciclo periférico del gráfico. Se aplica una forma del teorema de Wagner para menores bipartitos: un grafo bipartito G es un grafo plano si y sólo si no tiene el grafo de utilidad K 3,3 como menor bipartito. [30]
El problema de decidir si un gráfico G contiene H como menor es NP-completo en general; por ejemplo, si H es un gráfico de ciclo con el mismo número de vértices que G , entonces H es menor de G si y sólo si G contiene un ciclo hamiltoniano . Sin embargo, cuando G es parte de la entrada pero H es fijo, se puede resolver en tiempo polinomial. Más específicamente, el tiempo de ejecución para probar si H es menor de G en este caso es O ( n 3 ), donde n es el número de vértices en G y la notación O grande oculta una constante que depende superexponencialmente de H ; [3] desde el resultado original de Graph Minors, este algoritmo se ha mejorado a tiempo O ( n 2 ). [31] Por lo tanto, al aplicar el algoritmo de tiempo polinómico para probar si un gráfico dado contiene alguno de los menores prohibidos, es teóricamente posible reconocer a los miembros de cualquier familia cerrada de menores en tiempo polinómico . Este resultado no se utiliza en la práctica ya que la constante oculta es tan grande (necesita tres capas de notación de flecha hacia arriba de Knuth para expresarse) que descarta cualquier aplicación, lo que lo convierte en un algoritmo galáctico . [32] Además, para aplicar este resultado de manera constructiva, es necesario saber cuáles son los menores prohibidos de la familia de grafos. [4] En algunos casos, los menores prohibidos son conocidos o computables. [33]
En el caso de que H sea un gráfico plano fijo , entonces podemos probar en tiempo lineal en un gráfico de entrada G si H es menor de G. [34] En los casos en los que H no es fijo, se conocen algoritmos más rápidos en el caso en que G es plano. [35]
