Menor (teoría de grafos)

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

En el lado izquierdo, se muestra el grafo completo con tres vértices $K_{3}$. Es creado por contracción de aristas a partir del grafo $IK_{3}$, que a su vez está contenido en $Y$. Entonces $K_{3}$ es un menor de $Y$

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 K₅ ni el grafo bipartito completo K_3,3.​ 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.​

Para cada grafo fijo H, es posible probar si H es un menor de un grafo de entrada G en complejidad temporal;​ junto con la caracterización menor prohibida, esto implica que cada propiedad del grafo preservada por eliminaciones y contracciones puede reconocerse en tiempo polinomial.​

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 H 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 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.​

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

Ejemplo

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):

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 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.​ 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.​

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.​

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.​ 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 $\scriptstyle O(nh{\sqrt {\log h}})$ aristas, y algunos K_h grafos sin menores tienen al menos esta cantidad de aristas.​ Por lo tanto, si H tiene h vértices, entonces los H grafos sin menores tienen grado medio $\scriptstyle O(h{\sqrt {\log h}})$ y, además $\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 $\scriptstyle O({\sqrt {n}})$ vértices cuya eliminación divide G en dos subgrafos (posiblemente desconectados) con como máximo ²ⁿ⁄₃ vértices por subgrafo.​ Aún más fuerte, para cualquier H fijo, los grafos sin menores de H tienen ancho de árbol $\scriptstyle O({\sqrt {n}})$.​

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.​ El caso k= 5 es una reformulación del teorema de los cuatro colores. La conjetura de Hadwiger ha sido probada para k ≤ 6,​ 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.​

Familias de grafos cerrados menores

Véase también: Teorema de Robertson-Seymour

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.​

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.​

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,​ 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,​ 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).​ 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.​ 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₅.​

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.​ 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 K₅ 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.​

La relación topológica menor no es un buen cuasi-ordenamiento en el conjunto de grafos finitos​ 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.​

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.​

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.​ 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.​

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.​ 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.​

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 K_3,3 como un menor bipartito.​

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(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;​ desde el resultado original de menores de grafos, este algoritmo se ha mejorado a un tiempo O(n²).​ 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.​ Además, para aplicar este resultado de manera constructiva, es necesario saber cuáles son los menores prohibidos de la familia del grafo.​ En algunos casos, los menores prohibidos son conocidos, o pueden computarse.​

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.​ En los casos en que H no es fija, se conocen algoritmos más rápidos en el caso en que G es plano.​

Véase también

• Snark (teoría de grafos)

Referencias

• Alon, Noga; Seymour, Paul; Thomas, Robin (1990), «A separator theorem for nonplanar graphs», Journal of the American Mathematical Society 3 (4): 801-808, JSTOR 1990903, MR 1065053, doi:10.2307/1990903 ..
• Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile (2015), Induced minors and well-quasi-ordering, Bibcode:2015arXiv151007135B, arXiv:1510.07135 ..
• Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980), «Hadwiger's conjecture is true for almost every graph», European Journal of Combinatorics 1 (3): 195-199, doi:10.1016/s0195-6698(80)80001-1, archivado desde el original el 18 de marzo de 2009 ..
• Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra (2014), «Crossings and planarization», en Tamassia, Roberto, ed., Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL ..
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004), «Diameter and treewidth in minor-closed graph families, revisited», Algorithmica 40 (3): 211-215, S2CID 390856, doi:10.1007/s00453-004-1106-1 ..
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2002), «1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor», Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), Lecture Notes in Computer Science 2462, Springer-Verlag, pp. 67-80, doi:10.1007/3-540-45753-4_8 .
• Diestel, Reinhard (2005), Graph Theory (3rd edición), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 ..
• Ding, Guoli (1996), «Excluding a long double path minor», Journal of Combinatorial Theory, Series B 66 (1): 11-23, MR 1368512, doi:10.1006/jctb.1996.0002 ..
• Eppstein, David (2000), «Diameter and treewidth in minor-closed graph families», Algorithmica 27 (3): 275-291, MR 1759751, S2CID 3172160, arXiv:math.CO/9907126, doi:10.1007/s004530010020 ..
• Fellows, Michael R.; Langston, Michael A. (1988), «Nonconstructive tools for proving polynomial-time decidability», Journal of the ACM 35 (3): 727-739, S2CID 16587284, doi:10.1145/44483.44491 ..
• Grohe, Martin (2003), «Local tree-width, excluded minors, and approximation algorithms», Combinatorica 23 (4): 613-632, S2CID 11751235, arXiv:math/0001128, doi:10.1007/s00493-003-0037-9 ..
• Hadwiger, Hugo (1943), «Über eine Klassifikation der Streckenkomplexe», Vierteljschr. Naturforsch. Ges. Zürich 88: 133-143 ..
• Hall, Dick Wick (1943), «A note on primitive skew curves», Bulletin of the American Mathematical Society 49 (12): 935-936, doi:10.1090/S0002-9904-1943-08065-2 ..
• Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (March 2012), «The disjoint paths problem in quadratic time», Journal of Combinatorial Theory, Series B 102 (2): 424-435, doi:10.1016/j.jctb.2011.07.004 .
• Kostochka, Alexandr V. (1982), «The minimum Hadwiger number for graphs with a given mean degree of vertices», Metody Diskret. Analiz. (en ruso) 38: 37-58 ..
• Kostochka, Alexandr V. (1984), «Lower bound of the Hadwiger number of graphs by their average degree», Combinatorica 4 (4): 307-316, S2CID 15736799, doi:10.1007/BF02579141 ..
• Lovász, László (2006), «Graph minor theory», Bulletin of the American Mathematical Society 43 (1): 75-86, doi:10.1090/S0273-0979-05-01088-8 ..
• Mader, Wolfgang (1967), «Homomorphieeigenschaften und mittlere Kantendichte von Graphen», Mathematische Annalen 174 (4): 265-268, S2CID 120261785, doi:10.1007/BF01364272 ..
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer, pp. 62-65, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4 ..
• Pegg, Ed, Jr. (2002), «Book Review: The Colossal Book of Mathematics», Notices of the American Mathematical Society 49 (9): 1084-1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756 ..
• Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), «Shallow excluded minors and improved graph decompositions», Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994), pp. 462-470 ..
• Reed, Bruce; Wood, David R. (2009), «A linear-time algorithm to find a separator in a graph excluding a minor», ACM Transactions on Algorithms 5 (4): Article 39, S2CID 760001, doi:10.1145/1597036.1597043 ..
• Robertson, Neil; Seymour, Paul (1983), «Graph minors. I. Excluding a forest», Journal of Combinatorial Theory, Series B 35 (1): 39-61, doi:10.1016/0095-8956(83)90079-5 ..
• Robertson, Neil; Seymour, Paul D. (1986), «Graph minors. V. Excluding a planar graph», Journal of Combinatorial Theory, Series B 41 (1): 92-114, doi:10.1016/0095-8956(86)90030-4 .
• Robertson, Neil; Seymour, Paul D. (1993), «Excluding a graph with one crossing», en Robertson, Neil; Seymour, Paul, eds., Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics 147, American Mathematical Society, pp. 669-675 ..
• Robertson, Neil; Seymour, Paul D. (1995), «Graph Minors. XIII. The disjoint paths problem», Journal of Combinatorial Theory, Series B 63 (1): 65-110, doi:10.1006/jctb.1995.1006 ..
• Robertson, Neil; Seymour, Paul D. (2003), «Graph Minors. XVI. Excluding a non-planar graph», Journal of Combinatorial Theory, Series B 89 (1): 43-76, doi:10.1016/S0095-8956(03)00042-X ..
• Robertson, Neil; Seymour, Paul D. (2004), «Graph Minors. XX. Wagner's conjecture», Journal of Combinatorial Theory, Series B 92 (2): 325-357, doi:10.1016/j.jctb.2004.08.001 ..
• Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), «Hadwiger's conjecture for K₆-free graphs», Combinatorica 13 (3): 279-361, S2CID 9608738, doi:10.1007/BF01202354 ..
• Thomas, Robin (1999), «Recent excluded minor theorems for graphs», Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser. 267, Cambridge: Cambridge Univ. Press, pp. 201-222, MR 1725004 ..
• Thomason, Andrew (1984), «An extremal function for contractions of graphs», Mathematical Proceedings of the Cambridge Philosophical Society 95 (2): 261-265, Bibcode:1983MPCPS..95..261T, doi:10.1017/S0305004100061521 ..
• Thomason, Andrew (2001), «The extremal function for complete minors», Journal of Combinatorial Theory, Series B 81 (2): 318-338, doi:10.1006/jctb.2000.2013 ..
• Wagner, Klaus (1937a), «Über eine Eigenschaft der ebenen Komplexe», Math. Ann. 114: 570-590, S2CID 123534907, doi:10.1007/BF01594196 ..
• Wagner, Klaus (1937b), «Über eine Erweiterung des Satzes von Kuratowski», Deutsche Mathematik 2: 280-285 ..

Enlaces externos

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

• Datos: Q905837
• Multimedia: Graph minors / Q905837