Teorema de Pontryagin-Kuratovsky

El teorema de Pontryagin-Kuratovsky , o teorema de Kuratovsky , es un teorema de la teoría de grafos que establece una condición necesaria y suficiente para que un grafo sea plano . Tiene una formulación equivalente en el lenguaje de los menores, el llamado teorema de Wagner .

El teorema establece que los gráficos K 5 ( gráfico completo en 5 vértices) y K 3,3 ( gráfico bipartito completo con 3 vértices en cada parte) son los únicos gráficos mínimos no planos.

Historia

Fue demostrado en 1930 por el matemático polaco Kazimir Kuratovsky [1] y en 1927 por el matemático soviético Lev Semyonovich Pontryagin , quien no publicó su prueba.

Definiciones preliminares

Un gráfico se llama plano si se puede dibujar en un plano bidimensional de modo que sus bordes no se crucen en pares.

Un grafo se llama subdivisión de un grafo si se puede obtener sumando vértices a sus aristas. $GRAMO'$ $GRAMO$ ${\ estilo de visualización G'}$ $GRAMO$

Redacción

Un grafo es plano si y solo si no contiene divisiones de un grafo completo con cinco vértices (K 5 ) y un grafo bipartito completo con tres vértices en cada parte (K 3,3 ).

Prueba

La propiedad 'el grafo contiene un subgrafo homeomorfo al grafo ' se abreviará como ' '. Elimine el borde ' ', reduzca el borde ' ' y elimine el vértice ' '. $GRAMO$ $H$ $G\supset H$ ${\ estilo de visualización Ge}$ ${\ estilo de visualización G / e}$ ${\ estilo de visualización Gx}$

La suficiencia en el teorema de Kuratowski se prueba por inducción sobre el número de aristas en un gráfico. El paso de inducción se sigue del enunciado, ya que si o o o para alguna arista e del gráfico , entonces o . La declaración 'for ' es obvia. Si , entonces , y si , entonces o . $Ge\supset K_{5}$ $Ge\supset K_{3,3}$ $G/e\supset K_{5}$ $G/e\supset K_{3,3}$ $GRAMO$ $G\supset K_{5}$ $G\supset K_{3,3}$ ${\ estilo de visualización Ge}$ $G/xy\supset K_{3,3}$ $G\supset K_{3,3}$ $G/xy\supset K_{5}$ $G\supset K_{5}$ $G\supset K_{3,3}$

Si un grafo conexo es isomorfo a ni , ni , y para cualquier borde del grafo ambos grafican y son planos, entonces planos.

GRAMO

K_{5}

K_{3,3}

mi

GRAMO

{\ estilo de visualización Ge}

{\ estilo de visualización G / e}

GRAMO

Lema sobre grafos de Kuratowski

Para un gráfico arbitrario, las siguientes tres condiciones son equivalentes: $k$

Para cualquier borde xy del gráfico , el gráfico no contiene un gráfico θ, y al menos dos bordes emergen de cada vértice del gráfico. $k$ ${\ Displaystyle Kxy}$ ${\ Displaystyle Kxy}$
Para cualquier arista de gráfico xy, el gráfico es un ciclo (que contiene vértices). $k$ ${\ Displaystyle Kxy}$ ${\ estilo de visualización n \ geq 3}$
$k$ isomorfo o . $K_{5}$ $K_{3,3}$

Dado que ni es isomorfo ni , entonces, según el lema del gráfico de Kuratowski, existe un borde del gráfico para el cual el gráfico contiene un vértice de grado menor que 2 (in ) o un subgrafo θ. $GRAMO$ $K_{5}$ $K_{3,3}$ ${\ estilo de visualización e = (xy)}$ $GRAMO$ ${\ estilo de visualización Gxy}$ ${\ estilo de visualización Gxy}$

Si en un grafo una o dos de sus aristas emergen de algún vértice, entonces la contracción de uno de ellos da como resultado un grafo plano, lo que significa que el grafo G también es plano. Por lo tanto, asumimos además que al menos tres de sus aristas emergen de cada vértice del grafo G. $GRAMO$

Por lo tanto, no hay vértices aislados en el gráfico, y si hay un vértice colgante p, entonces está conectado tanto a x como a y en el gráfico . Dibujemos un gráfico en un plano sin autointersecciones. Dado que hay tres aristas que salen de p en el gráfico, no hay aristas que vayan 'a un lado' del camino xpy desde p. 'Pintar' el borde xy a lo largo del camino xpy 'este lado' del mismo. Pongamos la imagen del gráfico G en el plano sin autointersecciones. ${\ estilo de visualización Gxy}$ $GRAMO$ $G-(xy)$ $GRAMO$

Considere ahora el caso cuando el gráfico contiene un θ-subgrafo. ${\ estilo de visualización Gxy}$

Del teorema de Jordan se deduce que cualquier gráfico plano divide el plano en un número finito de partes conectadas. Estas partes se llaman caras de un gráfico plano.

Dibujemos un gráfico sin autointersecciones en el plano . La imagen de la gráfica sobre el plano se obtiene borrando las aristas de la gráfica que salen del vértice xy. Denotar por el límite de esa cara (imagen) de la gráfica , que contiene el vértice xy de la gráfica . ${\ estilo de visualización G/xy}$ $Gxy=G/xy-xy$ ${\ estilo de visualización G/xy}$ ${\ estilo de visualización {\ barra {C}}}$ ${\ estilo de visualización G/xy-xy}$ ${\ estilo de visualización G/xy}$

Tenga en cuenta que el límite de una cara no puede contener un subgrafo θ.

(Esta afirmación se puede deducir del teorema de Jordan. Otra prueba se obtiene por contradicción: si el límite de una cara contiene un subgrafo θ, entonces tomamos un punto dentro de esta cara y lo conectamos con tres aristas con tres puntos en tres 'arcos ' del subgrafo θ. Obtenemos una imagen del grafo en planos sin autointersecciones, una contradicción.) $K_{3,3}$

Por lo tanto Entonces los bordes de la gráfica están en la cara (imagen) de la gráfica que no contiene el vértice xy. Entonces la gráfica divide el plano. Por lo tanto, hay un ciclo con respecto al cual el vértice xy se encuentra dentro (sin pérdida de generalidad) y alguna arista del grafo se encuentra fuera. $Gxy\neq {\bar{C}}$ $Gxy-{\bar{C}}$ $Gxy=G/xy-xy$ ${\ estilo de visualización {\ barra {C}}}$ $C\subconjunto {\bar {C))$ $Gxy-{\bar{C}}$

Denote por la unión de todos los bordes del gráfico que se encuentran fuera del ciclo . (Posiblemente, .) Podemos suponer que es un subgrafo en (y no solo en ). $R$ ${\ estilo de visualización G/xy}$ $C$ $Gxy-{\bar {C}}\neqR$ $R$ $GRAMO$ ${\ estilo de visualización Gxy}$

Se puede dibujar un gráfico en un plano sin autointersecciones. Podemos suponer que los bordes del gráfico G, que salen de x o y, en la imagen del gráfico se encuentran dentro del ciclo . $GR$ $GR$ $C$

Cada componente conectado del gráfico se cruza con un punto como máximo. ${\ estilo de visualización GxyRC}$ $C$

(Si este no es el caso, entonces hay un camino que conecta dos puntos en . En la imagen del gráfico, el camino correspondiente se encuentra dentro del ciclo . Por lo tanto, este camino divide el interior del ciclo en dos partes, una del cual contiene xy, y el otro no está en el borde, acotado ... Por lo tanto , una contradicción.) ${\ estilo de visualización GxyRC}$ $C$ ${\ estilo de visualización G/xy}$ $C$ $C$ ${\ estilo de visualización {\ barra {C}}}$ $C\nsubconjunto {\bar {C))$

Por lo tanto, podemos lanzar cada componente conexa del gráfico dentro del ciclo . Entonces el gráfico se puede dibujar dentro del bucle . Dibujemos afuera , como para la imagen del gráfico . Obtenemos una imagen de un gráfico en un plano sin autointersecciones. $C$ ${\ estilo de visualización GxyRC}$ ${\ estilo de visualización GRC}$ $C$ $R$ $C$ ${\ estilo de visualización G/xy}$ $GRAMO$

Variaciones y generalizaciones

El teorema de Wagner es otra formulación del teorema de Pontryagin-Kuratovsky, a través de menores .
El teorema de Robertson-Seymour .

Notas

↑ Kuratowski, Kazimierz (1930), Sur le problème des courbes gauches en topologie , Fund. Matemáticas. T. 15: 271–283 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf > Archivado el 23 de julio de 2018 en Wayback Machine .

Enlaces

A. B. Skopenkov. En torno al criterio de Kuratovsky para la planaridad de los gráficos // Ser de educación matemática . 3. - 2005. - T. 9 . - S. 116-128 . /arXiv:0802.3820 __ _
Yu. Makarychev, Una breve prueba del criterio de planaridad de grafos de Kuratowski, J. of Graph Theory, 25 (1997) 129-131.