Teorema de Kuratowski

Sobre subgrafos prohibidos en grafos planares

Una subdivisión de K _3,3 en el gráfico de Petersen generalizado G (9,2), que muestra que el gráfico no es planar.

En teoría de grafos , el teorema de Kuratowski es una caracterización matemática prohibida de grafos planos , llamada así por Kazimierz Kuratowski . Establece que un grafo finito es plano si y solo si no contiene un subgrafo que sea una subdivisión de (el grafo completo en cinco vértices ) o de (un grafo bipartito completo en seis vértices, tres de los cuales se conectan con cada uno de los otros tres, también conocido como grafo de utilidad ). ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Declaración

Un grafo plano es un grafo cuyos vértices pueden representarse por puntos en el plano euclidiano y cuyos bordes pueden representarse por curvas simples en el mismo plano que conectan los puntos que representan sus extremos, de modo que no hay dos curvas que se intersequen excepto en un extremo común. Los grafos planos suelen dibujarse con segmentos de línea recta que representan sus bordes, pero según el teorema de Fáry esto no hace ninguna diferencia en su caracterización teórica de grafos.

Una subdivisión de un grafo es un grafo formado al subdividir sus aristas en caminos de una o más aristas. El teorema de Kuratowski establece que un grafo finito es plano si no es posible subdividir las aristas de o , y luego posiblemente agregar aristas y vértices adicionales, para formar un grafo isomorfo a . De manera equivalente, un grafo finito es plano si y solo si no contiene un subgrafo que sea homeomorfo a o . ${\displaystyle G}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$ ${\displaystyle G}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Subgrafos de Kuratowski

Prueba sin palabras de que un grafo hipercubo no es plano utilizando los teoremas de Kuratowski o Wagner y encontrando subgrafos K ₅ (arriba) o K _3,3 (abajo)

Si es un grafo que contiene un subgrafo que es una subdivisión de o , entonces se conoce como un subgrafo de Kuratowski de . ^[1] Con esta notación, el teorema de Kuratowski se puede expresar sucintamente: un grafo es planar si y solo si no tiene un subgrafo de Kuratowski. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$ ${\displaystyle H}$ ${\displaystyle G}$

Los dos grafos y son no planos, como se puede demostrar mediante un análisis de caso o un argumento que involucre la fórmula de Euler . Además, la subdivisión de un grafo no puede convertir un grafo no plano en un grafo plano: si una subdivisión de un grafo tiene un dibujo plano, las trayectorias de la subdivisión forman curvas que pueden usarse para representar las aristas de sí mismo. Por lo tanto, un grafo que contiene un subgrafo de Kuratowski no puede ser plano. La dirección más difícil para demostrar el teorema de Kuratowski es demostrar que, si un grafo no es plano, debe contener un subgrafo de Kuratowski. ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$ ${\displaystyle G}$ ${\displaystyle G}$

Implicaciones algorítmicas

Un subgrafo de Kuratowski de un grafo no plano se puede encontrar en tiempo lineal , medido por el tamaño del grafo de entrada. ^[2] Esto permite verificar la exactitud de un algoritmo de prueba de planaridad para entradas no planas, ya que es sencillo probar si un subgrafo dado es o no un subgrafo de Kuratowski. ^[3] Por lo general, los grafos no planos contienen una gran cantidad de subgrafos de Kuratowski. La extracción de estos subgrafos es necesaria, por ejemplo, en algoritmos de ramificación y corte para la minimización de cruces. Es posible extraer una gran cantidad de subgrafos de Kuratowski en el tiempo dependiendo de su tamaño total. ^[4]

Historia

Kazimierz Kuratowski publicó su teorema en 1930. ^[5] El teorema fue demostrado independientemente por Orrin Frink y Paul Smith , también en 1930, ^[6] pero su prueba nunca fue publicada. El caso especial de los grafos planos cúbicos (para los cuales el único subgrafo prohibido mínimo es ) también fue demostrado independientemente por Karl Menger en 1930. ^[7] Desde entonces, se han descubierto varias nuevas pruebas del teorema. ^[8] ${\displaystyle K_{3,3}}$

En la Unión Soviética , el teorema de Kuratowski se conocía como teorema de Pontryagin-Kuratowski o teorema de Kuratowski-Pontryagin , ^{[9] ya que, según se informa,} Lev Pontryagin demostró el teorema de forma independiente alrededor de 1927. ^[10] Sin embargo, como Pontryagin nunca publicó su prueba, este uso no se ha extendido a otros lugares. ^[11]

Resultados relacionados

Un resultado estrechamente relacionado, el teorema de Wagner , caracteriza los grafos planares por sus menores en términos de los mismos dos grafos prohibidos y . Cada subgrafo de Kuratowski es un caso especial de un menor del mismo tipo, y aunque lo inverso no es cierto, no es difícil encontrar un subgrafo de Kuratowski (de un tipo u otro) a partir de uno de estos dos menores prohibidos; por lo tanto, estos dos teoremas son equivalentes. ^[12] ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Una extensión es el teorema de Robertson-Seymour .

Véase también

• Conjetura de Kelmans-Seymour , de que los grafos no planos 5-conexos contienen una subdivisión de ${\displaystyle K_{5}}$

Referencias

1. Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la London Mathematical Society , Tercera serie, 13 : 743–767, doi :10.1112/plms/s3-13.1.743, MR  0158387.
2. Williamson, SG (septiembre de 1984), "Búsqueda en profundidad y subgrafos de Kuratowski", J. ACM , 31 (4): 681–693, doi : 10.1145/1634.322451 , S2CID  8348222.
3. Mehlhorn, Kurt ; Näher, Stefan (1999), LEDA: una plataforma para computación combinatoria y geométrica, Cambridge University Press, pág. 510, ISBN 9780521563291.
4. Chimani, Markus; Mutzel, Petra ; Schmidt, Jens M. (2007), "Extracción eficiente de múltiples subdivisiones de Kuratowski", en Hong, Seok-Hee ; Nishizeki, Takao ; Quan, Wu (eds.), Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, 24-26 de septiembre de 2007, Documentos revisados , Lecture Notes in Computer Science , vol. 4875, Springer, págs. 159–170, doi : 10.1007/978-3-540-77537-9_17 , ISBN 978-3-540-77536-2
5. Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF) , Fondo. Matemáticas. (en francés), 15 : 271–283, doi :10.4064/fm-15-1-271-283.
6. Frink, Orrin ; Smith, Paul A. (1930), "Gráficos no planos irreducibles", Boletín de la AMS , 36 : 214
7. Menger, Karl (1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen", Anzeiger der Akademie der Wissenschaften en Viena , 67 : 85–86
8. Thomassen, Carsten (1981), "Teorema de Kuratowski", Journal of Graph Theory , 5 (3): 225–241, doi :10.1002/jgt.3190050304, MR  0625064.
9. Burstein, Michael (1978), "Teorema de Kuratowski-Pontrjagin sobre grafos planares", Journal of Combinatorial Theory, Serie B , 24 (2): 228–232, doi :10.1016/0095-8956(78)90024-2
10. Kennedy, John W.; Quintas, Louis V.; Sysło, Maciej M. (1985), "El teorema sobre grafos planares", Historia Mathematica , 12 (4): 356–368, doi : 10.1016/0315-0860(85)90045-X
11. Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2010), Gráficos y dígrafos (5ª ed.), CRC Press, p. 237, ISBN 9781439826270.
12. Bondy, JA ; Murty, USR (2008), Teoría de grafos, Textos de posgrado en matemáticas, vol. 244, Springer, pág. 269, ISBN 9781846289699.