Conde menor

Una asignatura secundaria en teoría de grafos  es un gráfico para un gráfico dado , que se puede formar quitando aristas y vértices y contrayendo aristas .

La teoría de los grafos menores comenzó con el teorema de Wagner , que establece que un grafo es plano si y solo si sus menores no pertenecen ni al grafo completo K 5 ni al grafo completo bipartito K 3,3 [1] [2] . Del teorema de Robertson-Seymour se deduce que existen análogos de la caracterización menor prohibida para cualquier propiedad de los gráficos que se conserva bajo la eliminación de bordes y la contracción [3] [4] .

Para cualquier gráfico H , se puede comprobar si H es un menor del gráfico de entrada G en tiempo polinomial [5] . Junto con la caracterización por menores prohibidos, se deduce que cualquier propiedad gráfica que se conserva bajo deleciones y contracciones puede ser reconocida en tiempo polinomial [6] .

Entre otros resultados y conjeturas utilizando grafos menores se encuentran el teorema de estructura de grafos , según el cual grafos que no contengan H como menor pueden formarse pegando partes más simples, y la conjetura de Hadwiger , que relaciona la imposibilidad de colorear grafos con la existencia de un gran gráfico completo como su menor. Las variantes importantes de los menores gráficos son los menores topológicos y los menores inmersos.

Definiciones

La contracción de bordes es una operación que elimina un borde de un gráfico y fusiona los extremos del borde en un solo vértice. Un grafo no dirigido H es menor de otro grafo no dirigido G si se puede obtener un grafo isomorfo a H a partir de G contrayendo aristas, eliminando algunas aristas y eliminando algunos vértices aislados. El orden en que se realizan las contracciones y eliminaciones en G no afecta el gráfico H resultante .

Los gráficos menores a menudo se estudian en el contexto más general de matroid minors . En este contexto, generalmente se supone que los gráficos están conectados, pueden tener bucles y múltiples bordes (es decir, se consideran multigrafos , no gráficos simples). Está prohibido tirar del lazo y quitar el filo . Con este enfoque, eliminar un borde deja el rango del gráfico sin cambios, mientras que contraer un borde siempre reduce el rango en uno.

En otros contextos (como en el estudio de pseudobosques , por ejemplo ), tiene sentido permitir que se eliminen los bordes cortantes y permitir que los gráficos se desconecten, pero también tiene sentido no permitir multigrafos. En esta versión de la teoría de grafos menores, el gráfico siempre se simplifica después de cualquier contracción de borde para eliminar bucles y múltiples bordes [7]

Ejemplo

En el siguiente ejemplo, el gráfico H es un menor del gráfico G :

h

GRAMO.

La siguiente figura ilustra esto. Primero, construimos un subgrafo de G eliminando los bordes punteados (y el vértice aislado resultante) y luego contrayendo el borde gris (uniendo los dos vértices que conecta el borde):

Principales resultados y conjeturas

Se puede verificar fácilmente que la relación de grafos menores forma un orden parcial en la clase de isomorfismo de grafos no dirigidos: la relación es transitiva (el menor de un grafo G es en sí mismo un menor de G ) y los gráficos G y H pueden ser el uno del otro. menores si son isomorfos, ya que cualquier operación no trivial con un menor quita aristas o vértices. Un resultado profundo de Neil Robertson y Paul Seymour establece que este orden parcial es, de hecho, un orden completamente cuasi-ordenado  — dada una lista infinita G 1 , G 2 ,… de grafos finitos, siempre hay dos índices i < j , tales que G i es un menor del grafo G j . Una formulación equivalente de la declaración es que cualquier conjunto de gráficos puede tener solo un número finito de elementos mínimos por una relación menor [8] . Este resultado prueba la conjetura conocida hasta ahora como la conjetura de Wagner. Wagner conjeturó mucho antes, pero lo publicó recién en 1970 [9] .

En el curso de la prueba, Seymour y Robertson también demostraron el teorema de la estructura del gráfico , en el que determinaron, para cualquier gráfico fijo H , la estructura aproximada de cualquier gráfico que no contenga H como menor. El enunciado del teorema es largo y enrevesado, pero en resumen, el teorema establece que dicho gráfico debe tener la estructura de una suma sobre camarillas de gráficos más pequeños, que se obtienen mediante una ligera modificación de gráficos incrustados en superficies de género acotado . Por lo tanto, su teoría establece una conexión fundamental entre grafos menores e incrustaciones topológicas de grafos [10] [11] .

Para cualquier gráfico H , los gráficos simples H-menor-free deben ser escasos , lo que significa que el número de aristas es menor que alguna constante multiplicada por el número de vértices [12] . Más específicamente, si H tiene h vértices, entonces un simple gráfico libre de n - vértices H -menor puede tener como máximo aristas, y algunos gráficos libres de Kh -menor tienen al menos ese número de aristas [13] . Así, si H tiene h vértices, entonces los grafos libres de H -menor tienen grado medio y, además, degeneración . Además, los gráficos libres de H -menores tienen un teorema de partición similar al teorema de partición de gráficos planos: para cualquier H fijo y cualquier gráfico G libre de H -menores de n vértices , se puede encontrar un subconjunto de vértices de tamaño , cuyos La eliminación divide el gráfico G en dos subgráficos (posiblemente desconectados) con un máximo de 2 n /3 vértices cada uno [14] . Aún más estrictamente, para cualquier H fijo, H -menor- los gráficos libres tienen un ancho de árbol [15] .

La conjetura de Hadwiger asume que si el grafo G no contiene un isomorfo menor a un grafo completo con k vértices, entonces el grafo G tiene una coloración regular en k  − 1 colores [16] . El caso k  = 5 es una reformulación del problema de los cuatro colores . La conjetura de Hadwiger ha sido probada para k  ≤ 6 [17] , pero no de forma general. Bolobas, Katlin y Erdős [18] llamaron al problema "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 de snark , que fue anunciado por Robertson, Sanders, Seymour y Thomas [19] . El teorema es un reforzamiento del teorema de los cuatro colores y fue presentado (como una conjetura) por Tutt y establece que cualquier gráfico sin puente regular de 3 que requiera cuatro colores para ser coloreado con líneas debe contener el gráfico de Petersen como un menor [20 ] [21] .

Familias de grafos cerrados en menores

Muchas familias de grafos tienen la propiedad de que cualquier menor de un grafo en F también está en F. En este caso, se dice que la clase de grafos es cerrada menor . Por ejemplo, para cualquier gráfico plano o gráfico incrustado en una superficie topológica fija , ni la eliminación de los bordes ni la contracción de los bordes puede aumentar el género de la incrustación. Así, los gráficos planares y los gráficos empotrables en cualquier superficie fija forman familias cerradas de forma menor.

Si F es una familia minoritariamente cerrada, entonces (debido a la propiedad de cuasi-ordenación completa de los menores) entre los grafos que no pertenecen a F , existe un conjunto finito X de grafos minoritariamente mínimos. Estos gráficos son menores prohibidos para F  : un gráfico pertenece a F si y solo si no contiene ningún gráfico de X como menores . Por lo tanto, cualquier familia F cerrada a menores puede caracterizarse como una familia de grafos libres de menores de X para algún conjunto finito X de menores prohibidos [3] [4] .

Un ejemplo bien conocido de este tipo de caracterización es el Teorema de Wagner , que caracteriza grafos planos como grafos que no tienen ni K 5 ni K 3,3 como menores [1] [2] .

En algunos casos, las propiedades de los gráficos en una familia menor cerrada pueden estar estrechamente relacionadas con las propiedades de los menores excluidos. Por ejemplo, una familia cerrada menor de grafos F tiene un camino acotado si y solo si la familia prohibida de la familia incluye un bosque [22] , F tiene una profundidad de árbol acotada si y solo si los menores prohibidos incluyen una unión de caminos desacoplada , F tiene un ancho de árbol acotado si y solo si sus menores prohibidos incluyen un gráfico plano [23] , 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 se vuelve plano cuando el vértice) [24] [25] . Si H se puede dibujar en el plano con una sola intersección (es decir, el número de intersecciones del gráfico es igual a uno), entonces para gráficos libres de H -menor, el teorema de estructura simplificada es cierto, según el cual tales gráficos son una suma de camarilla de gráficos planares y gráficos con un ancho de árbol acotado [26] [27] . Por ejemplo, tanto K 5 como K 3,3 tienen un número de intersección de uno, y como mostró Wagner, los gráficos libres de K 5 son exactamente las sumas de 3 clicas de gráficos planos y un gráfico de Wagner de ocho vértices , mientras que aquellos libres de Los gráficos K 3,3 son exactamente las sumas de 2 clicas de los gráficos planos y K 5 [28] .

Variaciones

Menores topológicos

Un grafo H se llama topológico menor de un grafo G si el grafo de subdivisión de H es isomorfo a un subgrafo de G [29] . Es fácil ver que cualquier menor topológico es un menor (en el sentido habitual). Lo contrario, sin embargo, generalmente no es cierto (por ejemplo, el grafo completo K 5 en el grafo de Petersen es un menor, pero no es un menor topológico), pero se cumple para un grafo con un grado máximo que no exceda de tres [30] .

La relación de los menores topológicos no está completamente cuasi-ordenada sobre el conjunto de grafos finitos [31] , y por lo tanto el resultado de Robertson y Seymour es inaplicable a los menores topológicos. Sin embargo, es fácil construir caracterizaciones por menores topológicos prohibidos finitos a partir de una caracterización por menores prohibidos finitos.

Menor sumergido

La operación gráfica, llamada elevación , es un concepto central en el concepto de inmersión . El levantamiento es una operación en los bordes adyacentes. Dados tres vértices v , u y w , donde (v, u) y (u, w)  son aristas del gráfico, levantar vuw , o equivalentemente (v, u), (u, w)  es una operación que elimina dos aristas (v , u) y (u, w) y agrega un borde (v, w) . En el caso de que la arista (v, w) ya esté presente, v y w estarán conectadas por otra arista, por lo que la operación es esencialmente una operación multigráfica.

En el caso en que el grafo H pueda obtenerse del grafo G mediante una secuencia de operaciones de levantamiento (sobre G ) y luego encontrar un subgrafo isomorfo, decimos que H es un menor sumergido del grafo G .

Existe otra forma de definir a los menores sumergidos, que equivale a la operación de levantamiento. Decimos que H es un menor sumergido de un grafo G si existe una aplicación inyectiva de los vértices de H a los vértices de G tal que las imágenes de los elementos adyacentes de H están conectadas en G por caminos que no tienen aristas comunes.

La relación de menores sumergidos está completamente cuasi-ordenada sobre el conjunto de grafos finitos, por lo que los resultados de Roebrtson y Seymour son aplicables a menores sumergidos. Además, esto significa que toda familia cerrada en menores inmersos se caracteriza por una familia finita de menores inmersos prohibidos.

En la visualización de gráficos, los menores sumergidos aparecen como planarizaciones de gráficos no planos  : a partir del dibujo de un gráfico en un plano con intersecciones, se puede formar un menor sumergido reemplazando cada punto de intersección con un nuevo vértice y dividiendo cada borde cruzado. en un camino. Esto permite que los métodos de dibujo de gráficos planos se extiendan a gráficos no planos [32] .

menores superficiales

Un menor superficial de un grafo G  es un menor en el que los bordes del grafo G , contraídos para obtener el menor, forman subgrafos disjuntos de pequeño diámetro . Los menores superficiales forman una especie de puente entre los menores de grafos y los subgrafos, en el sentido de que los menores superficiales de alta profundidad son los mismos tipos habituales de menores, mientras que los menores superficiales de profundidad cero son exactamente subgrafos [33] . También permiten que la teoría de los grafos menores se extienda a clases de grafos, como los grafos de 1 plano , que no están cerrados en la toma de menores [34] .

Algoritmos

El problema de decidibilidad de si un grafo H está contenido en un grafo G como menor es, en general, NP-completo. Por ejemplo, si H es un 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 gráfico hamiltoniano . Sin embargo, si G es una entrada y H es fijo, el problema se puede resolver en tiempo polinomial. Más específicamente, el tiempo de ejecución para comprobar 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 O grande oculta una constante que depende superexponencialmente de H [5] . Debido a un resultado en grafos menores, este algoritmo mejora a O ( n 2 ) [35] . Así, al aplicar un algoritmo de tiempo polinomial para comprobar si un grafo dado contiene alguno de los menores prohibidos, es posible reconocer a los miembros de cualquier familia menor-cerrada en tiempo polinomial . Sin embargo, para aplicar constructivamente este resultado, es necesario conocer los menores prohibidos de la familia de los gráficos [6] .

Notas

  1. ↑ 12 Lovász , 2006 , pág. 77.
  2. ↑ 12 Wagner, 1937a .
  3. ↑ 1 2 Lovász, 2006 , Vol. 4, pág. 78.
  4. ↑ 12 Robertson , Seymour, 2004 .
  5. ↑ 12 Robertson , Seymour, 1995 .
  6. ↑ 12 becarios , Langston, 1988 .
  7. ↑ Lovász (2006 ) se contradice. En la página 76 escribe que "se permiten aristas y bucles paralelos", pero en la página 77 afirma que "un gráfico es un bosque si y solo si no contiene el triángulo K 3 como menor", lo cual solo es cierto para simples gráficos
  8. ↑ Diestel (2005 ), Capítulo 12: Menores, árboles y WQO; Robertson, Seymour (2004 ).
  9. ↑ Lovász, 2006 , pág. 76.
  10. ↑ Lovász, 2006 , pág. 80-82.
  11. ↑ Robertson, Seymour, 2003 .
  12. ↑ Mader, 1967 .
  13. ↑ Kostochka, 1984 ; Thomason, 1984 ; Thomason, 2001 .
  14. ↑ Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Caña, Madera, 2009 .
  15. ↑ Grohe, 2003 .
  16. ↑ Hadwiger, 1943 .
  17. ↑ Robertson, Seymour, Thomas, 1993 .
  18. ↑ Bollobás, Catlin, Erdős, 1980 .
  19. ↑ Sin embargo, a partir de 2012, la prueba aún no se ha publicado.
  20. ↑ Tomás, 1999 .
  21. ↑ Pegg, 2002 .
  22. ↑ Robertson, Seymour, 1983 .
  23. ↑ Lovász (2006 ), Teorema 9, p. 81; Robertson, Seymour (1986 ).
  24. ↑ Epstein, 2000 .
  25. ↑ Demaine, Hajiaghayi, 2004 .
  26. ↑ Robertson, Seymour, 1993 .
  27. ↑ Demaine, Hajiaghayi, Thilikos, 2002 .
  28. ↑ Wagner, 1937a ; Sala, 1943 .
  29. ↑ Diestel, 2005 , pág. veinte.
  30. ↑ Diestel, 2005 , pág. 22
  31. ↑ Ding, 1996 .
  32. ↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014 .
  33. ↑ Nešetřil, de Méndez, 2012 .
  34. ↑ Nešetřil, de Méndez, 2012 , p. 319-321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012 .

Literatura

Enlaces