Teorema de wagner

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar
K5 (izquierda) y K3,3 (derecha) como menores del gráfico no plano Petersen (pequeños círculos de colores y bordes negros sólidos). Los menores pueden formarse eliminando el vértice rojo y los bordes contratantes dentro de cada círculo amarillo.
Un cúmulo de dos gráficos plano y el gráfico Wagner, formando un K5- grafito libre.

En teoría de grafos, el teorema de Wagner es una caracterización matemática de grafos planos prohibidos, que lleva el nombre de Klaus Wagner, y que establece que un grafo finito es plano si y sólo si sus menores no incluyen ninguno de los dos. K5 (el gráfico completo en cinco vértices) ni K3,3 (el gráfico de utilidad, un gráfico completo gráfico bipartito en seis vértices). Este fue uno de los primeros resultados en la teoría de grafos menores y puede verse como un precursor del teorema de Robertson-Seymour.

Definiciones y declaraciones

Una incrustación plana de un gráfico dado es un dibujo del gráfico en el plano euclidiano, con puntos para sus vértices y curvas para sus aristas, de tal manera que las únicas intersecciones entre pares de aristas están en un punto final común de los dos bordes. Un gráfico menor de un gráfico dado es otro gráfico formado eliminando vértices, eliminando aristas y contrayendo aristas. Cuando se contrae una arista, sus dos puntos finales se fusionan para formar un solo vértice. En algunas versiones de la teoría de grafos menores, el gráfico resultante de una contracción se simplifica eliminando los bucles propios y las adyacencias múltiples, mientras que en otras versiones se permiten los multigrafos, pero esta variación no supone ninguna diferencia para el teorema de Wagner. El teorema de Wagner establece que todo grafo tiene una incrustación plana o una menor de uno de dos tipos, el grafo completo K5 o el grafo bipartito completo < i>K3,3. (También es posible que un solo gráfico tenga ambos tipos de menores).

Si un gráfico dado es plano, también lo son todos sus menores: la eliminación de vértices y aristas obviamente preserva la planaridad, y la contracción de las aristas también se puede realizar de manera que preserve la planaridad, dejando uno de los dos puntos finales del borde contraído en Coloque y enrute todos los bordes que incidieron en el otro punto final a lo largo del camino del borde contraído. Un gráfico no plano menor-mínimo es un gráfico que no es plano, pero en el que todos los menores propios (menores formados por al menos una deleción o contracción) son planos. Otra forma de enunciar el teorema de Wagner es que sólo hay dos gráficas no planas mínimas menores, K5 y K< sub>3,3.

Otro resultado también conocido como teorema de Wagner establece que un grafo de cuatro conexos es plano si y sólo si no tiene ningún K5 menor. Es decir, al asumir un mayor nivel de conectividad, el gráfico K3,3 puede hacerse innecesario en la caracterización, dejando solo un único menor prohibido, K. 5. En consecuencia, la conjetura de Kelmans-Seymour establece que un grafo de 5 conexos es plano si y sólo si no tiene K5 como menor topológico.

Historia y relación con el teorema de Kuratowski

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

Wagner publicó ambos teoremas en 1937, después de la publicación en 1930 del teorema de Kuratowski, según el cual un grafo es plano si y sólo si no contiene como subgrafo una subdivisión de uno de los mismos dos prohibidos. gráficas K5 y K3,3. En cierto sentido, el teorema de Kuratowski es más fuerte que el teorema de Wagner: una subdivisión se puede convertir en una menor del mismo tipo contrayendo todos los bordes menos uno en cada camino formado por el proceso de subdivisión, pero convirtiendo un minor en una subdivisión del mismo tipo no siempre es posible. Sin embargo, en el caso de las dos gráficas K5 y K3,3, es sencillo demostrar que un grafo que tiene al menos uno de estos dos grafos como menor también tiene al menos uno de ellos como subdivisión, por lo que los dos teoremas son equivalentes.

Implicaciones

Una consecuencia de la versión más fuerte del teorema de Wagner para grafos de cuatro conexos es caracterizar los grafos que no tienen un K5 menor. El teorema se puede reformular para afirmar que cada gráfico de este tipo es plano o se puede descomponer en partes más simples. Usando esta idea, las gráficas libres menores K5 se pueden caracterizar como las gráficas que se pueden formar como combinaciones de gráficas planas y la gráfica de Wagner de ocho vértices, pegadas. juntos mediante operaciones de suma camarilla. Por ejemplo, K3,3 se puede formar de esta manera como una suma de camarilla de tres gráficos planos, cada uno de los cuales es una copia del gráfico tetraédrico K4.

El teorema de Wagner es un precursor importante de la teoría de los grafos menores, que culminó con la demostración de dos resultados profundos y de gran alcance: el teorema de la estructura de los grafos (una generalización del teorema de suma camarilla de Wagner). descomposición de K5-gráficos libres menores) y el teorema de Robertson-Seymour (una generalización de la caracterización menor prohibida de los gráficos planos, que establece que toda familia de gráficos se cierra bajo el operación de acogida de menores se caracteriza por un número finito de menores prohibidos). Los análogos del teorema de Wagner también se pueden extender a la teoría de las matroides: en particular, las mismas dos gráficas K5 y K 3,3 (junto con otras tres configuraciones prohibidas) aparecen en una caracterización de las matroides gráficas por matroides menores prohibidas.

Más resultados...
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save