Menor (teoría de grafos)

De testwiki
Ir a la navegación Ir a la búsqueda
En el lado izquierdo, se muestra el grafo completo con tres vértices K3. Es creado por contracción de aristas a partir del grafo IK3, que a su vez está contenido en Y. Entonces K3 es un menor de Y

En teoría de grafos, un grafo Plantilla:Mvar se denomina menor del grafo Plantilla:Mvar si se puede formar Plantilla:Mvar a partir de Plantilla:Mvar eliminando aristas y vértices y mediante la contracción de aristas.

La teoría de los menores de grafo comenzó con el teorema de Wagner, que afirma que un grafo es plano si y solo si sus menores no incluyen ni el grafo completo Plantilla:Math ni el grafo bipartito completo Plantilla:Math.[1] El teorema de Robertson-Seymour implica que existe una caracterización de menores prohibidos análogo para cada propiedad de los grafos que se conserva mediante eliminaciones y contracciones de arista.[2]

Para cada grafo fijo Plantilla:Mvar, es posible probar si Plantilla:Mvar es un menor de un grafo de entrada Plantilla:Mvar en complejidad temporal;[3] junto con la caracterización menor prohibida, esto implica que cada propiedad del grafo preservada por eliminaciones y contracciones puede reconocerse en tiempo polinomial.[4]

Otros resultados y conjeturas que involucran grafos menores incluyen el teorema de la estructura del grafo, según el cual los grafos que no tienen Plantilla:Mvar como menor pueden formarse pegando piezas más simples, y la conjetura de Hadwiger que relaciona la incapacidad de colorear un grafo con la existencia de un gran grafo completo como menor. Las variantes importantes de los menores de grafos incluyen los menores topológicos y los menores de inmersión.

Definiciones

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 Plantilla:Mvar es un menor de otro grafo no dirigido Plantilla:Mvar si se puede obtener un grafo isomorfo a Plantilla:Mvar de partir de Plantilla:Mvar 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 Plantilla:Mvar no afecta al grafo resultante Plantilla:Mvar.

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 Plantilla:Mvar se denomina monótona menor si, siempre que Plantilla:Mvar sea menor de Plantilla:Mvar, se tiene que Plantilla:Math.

Ejemplo

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

H.Grafo H

G. Grafo 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):

Transformación desde G hasta H

Principales resultados y conjeturas

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 Plantilla:Mvar es un menor del propio Plantilla:Mvar), y Plantilla:Mvar y Plantilla:Mvar 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 Plantilla:Math, entonces siempre existen dos índices Plantilla:Math tales que Plantilla:Mvar es un menor de Plantilla:Mvar. 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 Plantilla:Mvar la estructura aproximada de cualquier grafo que no tenga Plantilla:Mvar 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 Plantilla:Mvar, los grafos libres de menores simples de Plantilla:Mvar 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 Plantilla:Mvar tiene Plantilla:Mvar vértices, entonces un grafo simple de Plantilla:Mvar-vértices Plantilla:Mvar sin menores puede tener como máximo O(nhlog⁡h) aristas, y algunos Plantilla:Mvar grafos sin menores tienen al menos esta cantidad de aristas.[10] Por lo tanto, si Plantilla:Mvar tiene Plantilla:Mvar vértices, entonces los Plantilla:Mvar grafos sin menores tienen grado medio O(hlog⁡h) y, además O(hlog⁡h) degenerados. Además, los Plantilla:Mvar grafos sin menores tienen un teorema separador similar al teorema separador plano para grafos planos: para cualquier Plantilla:Mvar fijo y para cualquier grafo Plantilla:Mvar de Plantilla:Mvar-vértices sin menores de Plantilla:Mvar, es posible encontrar un subconjunto de O(n) vértices cuya eliminación divide Plantilla:Mvar en dos subgrafos (posiblemente desconectados) con como máximo Plantilla:Math vértices por subgrafo.[11] Aún más fuerte, para cualquier Plantilla:Mvar fijo, los grafos sin menores de Plantilla:Mvar tienen ancho de árbol O(n).[12]

La conjetura de Hadwiger en la teoría de grafos propone que si un grafo Plantilla:Mvar no contiene un isomorfo menor al grafo completo en Plantilla:Mvar vértices, entonces Plantilla:Mvar tiene un coloreado propio con Plantilla:Math colores.[13] El caso Plantilla:Math es una reformulación del teorema de los cuatro colores. La conjetura de Hadwiger ha sido probada para Plantilla:Math,[14] pero se desconoce en el caso general.Plantilla:Harvtxt 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]

Familias de grafos cerrados menores

Plantilla:VT

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 K5 ni K3,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 K5 como K3,3 tienen número de cruces uno, y como Wagner demostró, los grafos sin K5 son exactamente las sumas de 3-cliques de grafos planares y el grafo de Wagner de ocho vértices, mientras que los grafos sin K3,3 son exactamente las sumas de 2-cliques de grafos planos y K5.[20]

Variaciones

Menores topológicos

Un grafo H se denomina menor topológico de un grafo G si una subdivisión de H es isomorfa a un subgrafo de G.[21] Es fácil ver que todo menor topológico también es un menor. Sin embargo, lo contrario no es cierto en general (por ejemplo, el grafo completo K5 en el grafo de Petersen es menor pero no topológico), pero es válido para grafos con un grado máximo no superior a tres.[22]

La relación topológica menor no es un buen cuasi-ordenamiento en el conjunto de grafos finitosPlantilla:Sfnp y, por lo tanto, el resultado de Robertson y Seymour no se aplica a los menores topológicos. Sin embargo, es sencillo construir caracterizaciones topológicas secundarias prohibidas finitas a partir de caracterizaciones secundarias prohibidas finitas reemplazando cada conjunto de ramas con k aristas salientes por un árbol de k hojas que tiene un grado de descenso de al menos dos.

Menores inducidos

Un grafo H se denomina menor inducido de un grafo G si puede obtenerse a partir de un subgrafo inducido de G contrayendo aristas. De lo contrario, se dice que G está libre de menores inducidos por H.[23]

Inmersión menor

Una operación gráfica llamada levantamiento es central en un concepto llamado inmersiones. El levantamiento es una operación sobre aristas adyacentes. Dados tres vértices v, u y w, donde (v,u) y (u,w) son aristas en el grafo, el levantamiento de vuw, o equivalentemente de (v,u), (u,w) es la operación que borra las dos aristas (v,u) y (u,w) y agrega la arista (v,w). En el caso de que (v,w) ya estuviera presente, v y w ahora estarán conectados por más de una arista y, por lo tanto, esta operación es intrínsecamente una operación de grafos múltiples.

En el caso de que se pueda obtener un grafo H a partir de un grafo G mediante una secuencia de operaciones de elevación (sobre G) y luego encontrar un subgrafo isomorfo, se dice que H es una inmersión menor de G.

Hay otra forma de definir los menores de inmersión, que es equivalente a la operación de levantamiento. Se dice que H es una inmersión menor de G si existe una aplicación inyectiva de vértices en H a vértices en G donde las imágenes de elementos adyacentes de H están conectadas en G por caminos disjuntos en las aristas.

La relación menor de inmersión es un casi buen ordenamiento en el conjunto de grafos finitos y, por lo 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 dibujo de grafos, los menores de inmersión surgen como los planarizados de grafos no planares: a partir de un 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 cruce de aristas en un camino. Esto permite que los métodos de dibujo de grafos planos se extiendan a grafos no planos.Plantilla:Sfnp

Menores superficiales

Un menor superficial de un grafo G es aquel en el que las aristas de G que se contrajeron para formar el menor forman una colección de subgrafos disjuntos con diámetro bajo. Los menores superficiales se interpolan entre las teorías de grafos menores y subgrafos, en el sentido de que los menores superficiales con gran profundidad coinciden con el tipo habitual de grafos menores, mientras que los menores superficiales con profundidad cero son exactamente los subgrafos.[24] También permiten extender la teoría de los menores de grafos a clases de grafos como los grafos 1-planos que no están cerrados tomando menores.[25]

Condiciones de paridad

Una definición alternativa y equivalente de un grafo menor es que H es un menor de G siempre que los vértices de H se puedan representar mediante una colección de subárboles disjuntos de vértices de G, tal que si dos vértices son adyacentes en H, existe una arista con sus extremos 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 arista de G dentro de un subárbol esté correctamente coloreada (sus extremos tengan colores diferentes) y cada arista de G que representa una adyacencia entre dos subárboles sea monocromática (que ambos extremos sean del mismo color). A diferencia del tipo habitual de grafos menores, los grafos con menores impares prohibidos no son necesariamente escasos.[26] La conjetura de Hadwiger, de que grafos k cromáticos necesariamente contienen grafos completos de k vértices como menores, también ha sido estudiada desde el punto de vista de los menores impares.[27]

Una extensión diferente basada en la noción de la paridad de grafos menores es el concepto de menor bipartito, que produce un grafo bipartito siempre que el grafo inicial sea bipartito. Un grafo H es un menor bipartito de otro grafo G siempre que se pueda obtener H de G eliminando vértices, eliminando aristas y colapsando pares de vértices que estén a distancia dos uno del otro en un ciclo periférico del grafo. Se aplica una forma del teorema de Wagner para los menores bipartitos: un grafo bipartito G es un grafo plano si y solo si no tiene el problema de los tres servicios K3,3 como un menor bipartito.[28]

Algoritmos

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(n3), 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(n2).[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]

Véase también

Notas

Plantilla:Reflist

Referencias

Plantilla:Refbegin

Plantilla:Refend

Enlaces externos

Plantilla:Control de autoridades

  1. ↑ 1,0 1,1 Plantilla:Harvtxt, p. 77;Plantilla:Harvtxt.
  2. ↑ 2,0 2,1 Plantilla:Harvtxt, theorem 4, p. 78;Plantilla:Harvtxt.
  3. ↑ 3,0 3,1 Plantilla:Harvtxt.
  4. ↑ 4,0 4,1 Plantilla:Harvtxt.
  5. ↑ Plantilla:Harvtxt is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p. 76 that "parallel edges and loops are allowed" but on p. 77 he states that "a graph is a forest if and only if it does not contain the triangle Plantilla:Math as a minor", true only for simple graphs.
  6. ↑ Plantilla:Harvtxt, Chapter 12: Minors, Trees, and WQO;Plantilla:Harvtxt.
  7. ↑ Plantilla:Harvtxt, p. 76.
  8. ↑ Plantilla:Harvtxt, pp. 80–82;Plantilla:Harvtxt.
  9. ↑ Plantilla:Harvtxt.
  10. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt.
  11. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt.
  12. ↑ Plantilla:Harvtxt
  13. ↑ Plantilla:Harvtxt.
  14. ↑ Plantilla:Harvtxt.
  15. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt.
  16. ↑ Plantilla:Harvtxt.
  17. ↑ Plantilla:Harvtxt, Theorem 9, p. 81;Plantilla:Harvtxt.
  18. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt.
  19. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt.
  20. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt.
  21. ↑ Plantilla:Harvnb
  22. ↑ Plantilla:Harvnb
  23. ↑ Plantilla:Harvtxt
  24. ↑ Plantilla:Harvtxt.
  25. ↑ Plantilla:Harvtxt, pp. 319–321.
  26. ↑ Plantilla:Citation.
  27. ↑ Plantilla:Citation.
  28. ↑ Plantilla:Citation.
  29. ↑ Plantilla:Harvtxt.
  30. ↑ Plantilla:Cite journal
  31. ↑ Plantilla:Cite journal See end of Section 5.
  32. ↑ Plantilla:Cite journal Primer epígrafe tras el Teorema 5.3
  33. ↑ Plantilla:Cite journal
Obtenido de «https://es.wiki.beta.math.wmflabs.org/w/index.php?title=Menor_(teoría_de_grafos)&oldid=12517»