Menor (teoría de grafos)

Una contracción de arista es una operación que elimina una arista de un grafo mientras fusiona simultáneamente los dos vértices que estaba conectando. Un grafo H es un menor de otro grafo no dirigido G si se puede obtener un grafo isomorfo a H de partir de G contrayendo algunas aristas, eliminando algunas aristas y eliminando algunos vértices aislados. El orden en que se realiza una secuencia de dichas contracciones y eliminaciones en G no afecta al grafo resultante H.

Los grafos menores a menudo se estudian en el contexto más general de los menores matroides. En este contexto, es común suponer que todos los grafos están conectados, estando permitidos bucles y aristas múltiples (es decir, son multigrafos en lugar de grafos simples); la contracción de un bucle y la eliminación de una arista de corte son operaciones prohibidas. Este punto de vista tiene la ventaja de que las eliminaciones de arista dejan el rango de un grafo sin cambios, y las contracciones de arista siempre reducen el rango en uno.

En otros contextos (como en el estudio de pseudobosques) tiene más sentido permitir la eliminación de una arista de corte y permitir grafos desconectados, pero prohibir los multigrafos. En esta variación de la teoría de grafos menores, un grafo siempre se simplifica después de cualquier contracción de arista para eliminar sus bucles propios y aristas múltiples.[5]

Una función f se denomina monótona menor si, siempre que H sea menor de G, se tiene que f(H) ≤ f(G).

En el siguiente ejemplo, el grafo H es menor del grafo G:

H.

G.

El siguiente diagrama ilustra esto. Primero se construye un subgrafo de G eliminando las aristas discontinuas (y el vértice aislado resultante), y luego se contrae la arista gris (fusionando los dos vértices que conecta):

Es sencillo verificar que la relación ser grafo menor forma un conjunto parcialmente ordenado sobre las clases de isomorfismos de grafos finitos no dirigidos: es transitiva (un menor de un menor de G es un menor del propio G), y G y H solo pueden ser menores entre sí si son isomorfos, porque cualquier operación menor no trivial elimina aristas o vértices. Un resultado profundo hallado por Neil Robertson y Paul Seymour establece que este orden parcial es en realidad un casi buen orden: si se da una lista infinita de grafos finitos (G₁, G₂, …), entonces siempre existen dos índices i < j tales que G_i es un menor de G_j. Otra forma equivalente de afirmar esto es que cualquier conjunto de grafos puede tener solo un número finito de elementos mínimos bajo el orden menor.[6] Este resultado demostró una conjetura anteriormente conocida como la conjetura de Wagner, en honor a Klaus Wagner; quien la había planteado mucho antes, aunque se publicó en 1970.[7]

En el curso de su demostración, Seymour y Robertson también probaron el teorema de la estructura de grafo, en el que determinaron para cualquier grafo fijo H la estructura aproximada de cualquier grafo que no tenga H como menor. El enunciado del teorema es en sí largo y complicado, pero en resumen establece que tal grafo debe tener la estructura de una suma de cliques de grafos más pequeños que se modifican ligeramente a partir de grafos embebidos en superficies de genus acotados.

Así, su teoría establece conexiones fundamentales entre grafos menores y embebidos topológicos de grafos.[8]

Para cualquier grafo H, los grafos libres de menores simples de H deben ser densos, 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 grafo simple de n-vértices H sin menores puede tener como máximo ${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$ aristas, y algunos K_h grafos sin menores tienen al menos esta cantidad de aristas.[10] Por lo tanto, si H tiene h vértices, entonces los H grafos sin menores tienen grado medio ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ y, además ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ degenerados. Además, los H grafos sin menores tienen un teorema separador similar al teorema separador plano para grafos planos: para cualquier H fijo y para cualquier grafo G de n-vértices sin menores de H, es posible encontrar un subconjunto de ${\displaystyle \scriptstyle O({\sqrt {n}})}$ vértices cuya eliminación divide G en dos subgrafos (posiblemente desconectados) con como máximo ²ⁿ⁄₃ vértices por subgrafo.[11] Aún más fuerte, para cualquier H fijo, los grafos sin menores de H tienen ancho de árbol ${\displaystyle \scriptstyle O({\sqrt {n}})}$.[12]

La conjetura de Hadwiger en la teoría de grafos propone que si un grafo G no contiene un isomorfo menor al grafo completo en k vértices, entonces G tiene un coloreado propio 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 calificó como "uno de los problemas sin resolver más profundos en la teoría de grafos". Otro resultado que relaciona el teorema de los cuatro colores con grafos menores es el teorema del snark anunciado por Robertson, Sanders, Seymour y Thomas, un refuerzo del teorema de los cuatro colores conjeturado por W. T. Tutte y que establece que cualquier grafo 3-regular sin puentes que requiera cuatro colores en un coloreado de aristas debe tener el grafo de Petersen como menor.[15]

Muchas familias de grafos tienen la propiedad de que todo menor de un grafo en F también está en F; se dice que dicha clase es menor cerrada. Por ejemplo, en cualquier grafo plano, o en cualquier embebido de un grafo en una superficie topológica fija, ni la eliminación de aristas ni la contracción de aristas permiten aumentar el genus del embebido; por lo tanto, los grafos planos y los grafos embebibles en cualquier superficie fija forman familias cerradas de menores.

Si F es una familia cerrada de menores, entonces (debido a la propiedad de buen cuasi-ordenamiento de los menores) entre los grafos que no pertenecen a F hay un conjunto finito X de grafos menores mínimo. Estos grafos son menores prohibidos para F: un grafo pertenece a F si y solo si no contiene como menor ningún grafo de X. Es decir, toda familia cerrada de menores F se puede caracterizar como la familia de grafos sin los menores de X 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 los grafos planos como aquellos que no tienen K₅ ni K_3,3 como menores.[1]

En algunos casos, las propiedades de los grafos en una familia cerrada de menores pueden estar estrechamente relacionadas con las propiedades de sus menores excluidos. Por ejemplo, una familia de grafos cerrados menores F tiene acotado su ancho de ruta si y solo si sus elementos menores prohibidos incluyen un bosque,[16] F tiene acotada su profundidad de árbol si y solo si sus elementos menores prohibidos incluyen una unión disjunta de grafos camino, F tiene ancho de árbol acotado si y solo si sus menores prohibidos incluyen un grafo plano,[17] y F tiene un ancho de árbol local acotado (una relación funcional entre su diámetro y el ancho del árbol) si y solo si sus menores prohibidos incluyen un grafo de ápice (un grafo que puede volverse plano eliminando un solo vértice).[18] Si H se puede dibujar en el plano con un solo cruce (es decir, tiene número de cruce uno), entonces los grafos de H sin menores tienen un teorema de estructura simplificado en el que se forman como suma de cliques de grafos planos y grafos de ancho de árbol acotado.[19] Por ejemplo, tanto K₅ como K_3,3 tienen número de cruces uno, y como Wagner demostró, los grafos sin K₅ son exactamente las sumas de 3-cliques de grafos planares y el grafo de Wagner de ocho vértices, mientras que los grafos sin K_3,3 son exactamente las sumas de 2-cliques de grafos planos y K₅.[20]

El problema de decisión de si un grafo G contiene H como menor es NP-completo en general; por ejemplo, si H es un grafo ciclo con el mismo número de vértices que G, entonces H es un menor de G si y solo si G contiene un camino 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³), 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 menores de grafos, este algoritmo se ha mejorado a un tiempo O(n²).[29] Por lo tanto, al aplicar el algoritmo de tiempo polinomial para probar si un grafo dado contiene alguno de los menores prohibidos, es teóricamente posible reconocer a los miembros de cualquier familia cerrada menor en tiempo polinómico. Este resultado no se usa en la práctica, ya que la constante oculta es tan grande (necesita tres capas en la notación flecha de Knuth para expresarse) que descarta cualquier aplicación, convirtiéndola en un algoritmo galáctico.[30] Además, para aplicar este resultado de manera constructiva, es necesario saber cuáles son los menores prohibidos de la familia del grafo.[4] En algunos casos, los menores prohibidos son conocidos, o pueden computarse.[31]

En el caso de que H sea un grafo plano fijo, entonces se puede probar en tiempo lineal en un grafo de entrada G si H es un menor de G.[32] En los casos en que H no es fija, se conocen algoritmos más rápidos en el caso en que G es plano.[33]

• Weisstein, Eric W. «Graph Minor». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.