En la teoría de grafos , el teorema de Kuratowski es un matemático caracterización gráfico prohibido de grafos planos , el nombre de Kazimierz Kuratowski . Establece que un grafo finito es plano si y solo si no contiene un subgrafo que sea una subdivisión de K 5 (el grafo completo en cinco vértices ) o de K 3,3 ( grafo bipartito completo en seis vértices, tres de los cuales conectarse a cada uno de los otros tres, también conocido como gráfico de utilidad ).
Declaración
Un gráfico plano es un gráfico cuyos vértices se pueden representar mediante puntos en el plano euclidiano , y cuyas aristas se pueden representar mediante curvas simples en el mismo plano que conectan los puntos que representan sus puntos finales, de modo que no se cruzan dos curvas excepto en un punto final común. Los gráficos planos a menudo se dibujan 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 de la teoría de gráficos.
Una subdivisión de un gráfico es un gráfico que se forma al subdividir sus bordes en rutas de uno o más bordes. Estados teorema de kuratowski que un grafo finito G es planar si no es posible subdividir los bordes de K 5 o K 3,3 , y luego, posiblemente, añadir bordes y vértices adicionales, para formar un gráfico isomorfo a G . De manera equivalente, un grafo finito es plano si y solo si no contiene un subgrafo que sea homeomorfo a K 5 o K 3,3 .
Subgrafos de Kuratowski
Si G es un gráfico que contiene un subgrafo H que es una subdivisión de K 5 o K 3,3 , entonces H es conocido como un subgrafo Kuratowski de G . [1] Con esta notación, el teorema de Kuratowski se puede expresar de manera sucinta: un gráfico es plano si y solo si no tiene un subgrafo de Kuratowski.
Las dos gráficas K 5 y K 3,3 no son planas, como puede mostrarse mediante un análisis de caso o un argumento que involucre la fórmula de Euler . Además, subdividir un gráfico no puede convertir un gráfico no plano en un gráfico plano: si una subdivisión de un gráfico G tiene un dibujo plano, las trayectorias de la subdivisión forman curvas que pueden usarse para representar los bordes de G en sí. Por lo tanto, un gráfico que contiene un subgráfico de Kuratowski no puede ser plano. La dirección más difícil para probar el teorema de Kuratowski es mostrar que, si un gráfico no es plano, debe contener un subgrafo de Kuratowski.
Implicaciones algorítmicas
Un subgrafo de Kuratowski de un gráfico no plano se puede encontrar en tiempo lineal , medido por el tamaño del gráfico 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 gráficos no planos contienen una gran cantidad de subgráficos 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 probado independientemente por Orrin Frink y Paul Smith , también en 1930, [6] pero su prueba nunca fue publicada. El caso especial de grafos planos cúbicos (para los cuales el único subgrafo mínimo prohibido es K 3,3 ) también fue probado independientemente por Karl Menger en 1930. [7] Desde entonces, se han descubierto varias nuevas demostraciones del teorema. [8]
En la Unión Soviética , el teorema de Kuratowski era conocido como el teorema de Pontryagin-Kuratowski o el teorema de Kuratowski-Pontryagin , [9] ya que el teorema fue probado de forma independiente por Lev Pontryagin alrededor de 1927. [10] Sin embargo, como Pontryagin nunca publicó su demostración , este uso no se ha extendido a otros lugares. [11]
Resultados relacionados
Un resultado estrechamente relacionado, el teorema de Wagner , caracteriza las gráficas planas por sus menores en términos de las mismas dos gráficas prohibidas K 5 y K 3,3 . Cada subgrafo de Kuratowski es un caso especial de un menor del mismo tipo, y aunque lo contrario no es cierto, no es difícil encontrar un subgrafo de Kuratowski (de un tipo u otro) de uno de estos dos menores prohibidos; por tanto, estos dos teoremas son equivalentes. [12]
Una extensión es el teorema de Robertson-Seymour .
Ver también
- Conjetura de Kelmans-Seymour , que 5 grafos no planos conectados contienen una subdivisión de K 5
Referencias
- ^ Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la Sociedad Matemática de Londres , tercera serie, 13 : 743–767, doi : 10.1112 / plms / s3-13.1.743 , MR 0158387.
- ^ Williamson, SG (septiembre de 1984), "Búsqueda en profundidad y subgrafos de Kuratowski", J. ACM , 31 (4): 681–693, doi : 10.1145 / 1634.322451.
- ^ Mehlhorn, Kurt ; Näher, Stefan (1999), LEDA: A Platform for Combinatorial and Geometric Computing , Cambridge University Press, pág. 510, ISBN 9780521563291.
- ^ Chimani, Markus; Mutzel, Petra ; Schmidt, Jens M. (2007), Extracción eficiente de múltiples subdivisiones de Kuratowski , págs. 159-170, doi : 10.1007 / 978-3-540-77537-9_17 Parámetro desconocido
|conference=
ignorado ( ayuda ) . - ^ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF) , Fondo. Matemáticas. (en francés), 15 : 271–283.
- ^ Frink, Orrin ; Smith, Paul A. (1930), "Gráficos no planares irreductibles", Boletín de la AMS , 36 : 214
- ^ Menger, Karl (1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen", Anzeiger der Akademie der Wissenschaften en Wien , 67 : 85–86
- ^ Thomassen, Carsten (1981), "Teorema de Kuratowski", Journal of Graph Theory , 5 (3): 225–241, doi : 10.1002 / jgt.3190050304 , MR 0625064.
- ^ Burstein, Michael (1978), "Teorema de Kuratowski-Pontrjagin en gráficas planas", Journal of Combinatorial Theory, Serie B , 24 : 228-232, doi : 10.1016 / 0095-8956 (78) 90024-2
- ^ Kennedy, John W .; Quintas, Louis V .; Sysło, Maciej M. (1985), "El teorema de las gráficas planas", Historia Mathematica , 12 : 356–368, doi : 10.1016 / 0315-0860 (85) 90045-X
- ^ Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (5.a ed.), CRC Press, pág. 237, ISBN 9781439826270.
- ^ Bondy, JA ; Murty, USR (2008), Teoría de grafos , Textos de posgrado en matemáticas, 244 , Springer, p. 269, ISBN 9781846289699.