El teorema de Kuratowski

A subdivision of K_3,3 en el gráfico generalizado Petersen G(9,2), mostrando que el gráfico no es plano.

En la teoría del gráfico, Teorema de Kuratowski es una caracterización matemática prohibida del gráfico de los gráficos planares, nombrado por Kazimierz Kuratowski. Afirma que un gráfico finito es planario si y sólo si no contiene un subgrafo que es una subdivisión de K5{displaystyle K_{5} (el gráfico completo en cinco vértices) o de K3,3{displaystyle K_{3,3} (un gráfico bipartito completo en seis vértices, tres de los cuales se conectan a cada uno de los otros tres, también conocido como el gráfico de utilidad).

Declaración

Un gráfico plano es un gráfico cuyos vértices pueden representarse mediante puntos en el plano euclidiano y cuyos bordes pueden representarse mediante curvas simples en el mismo plano que conectan los puntos que representan sus extremos, de modo que dos curvas no se intersecan 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 teórica de gráficos.

Una subdivisión de un gráfico es un gráfico formado por subdividir sus bordes en caminos de uno o más bordes. El teorema de Kuratowski declara que un gráfico finito G{displaystyle G. es plano si no es posible subdividir los bordes de K5{displaystyle K_{5} o K3,3{displaystyle K_{3,3}, y luego posiblemente añadir bordes adicionales y vertices, para formar un gráfico isomorfo a G{displaystyle G.. Equivalentemente, un gráfico finito es plano si y sólo si no contiene un subgrafo que es homeomorfo a K5{displaystyle K_{5} o K3,3{displaystyle K_{3,3}.

Subgrafos de Kuratowski

Prueba sin palabras de que un gráfico hipercubo no es plano usando los teoremas de Kuratowski o Wagner y encontrar o K₅ (top) or K_3,3 subgrafos

Si G{displaystyle G. es un gráfico que contiene un subgrafo H{displaystyle H. que es una subdivisión de K5{displaystyle K_{5} o K3,3{displaystyle K_{3,3}, entonces H{displaystyle H. es conocido como Subgrafo de Kuratowski de G{displaystyle G.. Con esta notación, el teorema de Kuratowski se puede expresar sucintamente: un gráfico es planar si y sólo si no tiene un subgrafo de Kuratowski.

Los dos gráficos K5{displaystyle K_{5} y K3,3{displaystyle K_{3,3} son no planas, como puede ser demostrado por un análisis de caso o un argumento que implica 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{displaystyle G. tiene un dibujo plano, los caminos de la forma de subdivisión curvas que pueden ser utilizados para representar los bordes de G{displaystyle G. en sí mismo. Por lo tanto, un gráfico que contiene un subgrafo de Kuratowski no puede ser planificado. La dirección más difícil en probar el teorema de Kuratowski es demostrar que, si un gráfico no es plano, debe contener un subgrafo de Kuratowski.

Implicaciones algorítmicas

Un subgráfico de Kuratowski de un gráfico no plano se puede encontrar en tiempo lineal, medido por el tamaño del gráfico de entrada. Esto permite verificar la corrección de un algoritmo de prueba de planaridad para entradas no planas, ya que es sencillo probar si un subgráfico dado es o no un subgráfico de Kuratowski. Por lo general, los gráficos 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.

Historia

Kazimierz Kuratowski publicó su teorema en 1930. El teorema fue probado independientemente por Orrin Frink y Paul Smith, también en 1930, pero su prueba nunca fue publicada. El caso especial de los gráficos de planos cúbicos (para los cuales el único subgrafo mínimo prohibido es K3,3{displaystyle K_{3,3}) también fue probado independientemente por Karl Menger en 1930. Desde entonces, se han descubierto varias pruebas nuevas del teorema.

En la Unión Soviética, el teorema de Kuratowski se conocía como teorema de Pontryagin-Kuratowski o teorema de Kuratowski-Pontryagin, como se informa, el teorema fue demostrado de forma independiente por Lev Pontryagin alrededor de 1927. Sin embargo, como Pontryagin nunca publicó su prueba, este uso no se ha extendido a otros lugares.

Resultados relacionados

Un resultado estrechamente relacionado, el teorema de Wagner, caracteriza los gráficos planares por sus menores en términos de los mismos dos gráficos prohibidos K5{displaystyle K_{5} y K3,3{displaystyle K_{3,3}. Cada subgrafo de Kuratowski es un caso especial de un menor del mismo tipo, y aunque el reverso no es cierto, no es difícil encontrar un subgrafo de Kuratowski (de un tipo o el otro) de uno de estos dos menores prohibidos; por lo tanto, estos dos teoremas son equivalentes.

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