En la teoría de grafos , Wagner es el teorema es una matemática caracterización gráfica prohibido de grafos planos , el nombre de Klaus Wagner , afirmando que un grafo finito es plano si y sólo si sus menores incluyen ni K 5 (el gráfico completo en cinco vértices ), ni K 3, 3 (el gráfico de utilidad , un gráfico bipartito completo 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 declaración
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 se encuentran en un punto final común de las dos aristas. . Un menor de un gráfico dado es otro gráfico que se forma eliminando vértices, eliminando bordes y contrayendo bordes. Cuando se contrae una arista, sus dos extremos se fusionan para formar un solo vértice. En algunas versiones de la teoría de grafos menor la gráfica resultante de una contracción se simplifica mediante la eliminación de la libre bucles y adyacencias múltiples, mientras que en otros la versión multigrafos están permitidos, pero esta variación no hace ninguna diferencia con el teorema de Wagner. El teorema de Wagner establece que cada gráfico tiene una incrustación plana, o una menor de uno de dos tipos, el gráfico completo K 5 o el gráfico bipartito completo K 3,3 . (También es posible que un solo gráfico tenga ambos tipos de menor).
Si un gráfico dado es plano, también lo son todos sus elementos secundarios: la eliminación de vértices y bordes obviamente preserva la planaridad, y la contracción del borde también se puede realizar de manera que conserve la planaridad, dejando uno de los dos puntos finales del borde contraído en su lugar y enrutado todos los bordes que inciden en el otro extremo a lo largo de la trayectoria 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 eliminación o contracción) son planos. Otra forma de enunciar el teorema de Wagner es que solo hay dos gráficos no planos menores-mínimos, K 5 y K 3,3 .
Otro resultado también conocido como teorema de Wagner establece que un gráfico de cuatro conexiones es plano si y solo si no tiene K 5 menor. Es decir, asumiendo un mayor nivel de conectividad, el gráfico K 3,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 gráfico de 5 conexiones es plano si y solo si no tiene K 5 como un menor topológico .
Historia y relación con el teorema de Kuratowski
Wagner publicó ambos teoremas en 1937, [1] después de la publicación en 1930 del teorema de Kuratowski , [2] según el cual un gráfico es plano si y solo si no contiene como subgráfico una subdivisión de uno de los mismos dos gráficos prohibidos. K 5 y K 3,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 todas las aristas menos una en cada camino formado por el proceso de subdivisión, pero convirtiendo una menor en una subdivisión del mismo tipo. no siempre es posible. Sin embargo, en el caso de los dos gráficos K 5 y K 3,3 , es sencillo demostrar que un gráfico que tiene al menos uno de estos dos gráficos como menor también tiene al menos uno de ellos como subdivisión, por lo que el dos teoremas son equivalentes. [3]
Trascendencia
Una consecuencia de la versión más sólida del teorema de Wagner para gráficos de cuatro conexiones es caracterizar los gráficos que no tienen un K 5 menor. El teorema puede reformularse diciendo que cada gráfico de este tipo es plano o puede descomponerse en partes más simples. Usando esta idea, las gráficas libres de K 5 -menores pueden caracterizarse como las gráficas que pueden formarse como combinaciones de gráficas planas y la gráfica de Wagner de ocho vértices , unidas por operaciones de suma de clique . Por ejemplo, K 3,3 se puede formar de esta manera como una clique-suma de tres gráficos planos, cada uno de los cuales es una copia del gráfico tetraédrico K 4 .
El teorema de Wagner es un precursor importante de la teoría de grafos menores, que culminó en las demostraciones de dos resultados profundos y de gran alcance: el teorema de la estructura del grafo (una generalización de la descomposición de Wagner por suma de clique de K 5 -grafos libres de menores) [ 4] y el teorema de Robertson-Seymour (una generalización de la caracterización menor prohibida de grafos planos, que establece que cada familia de grafos cerrada bajo la operación de tomar menores tiene una caracterización por un número finito de menores prohibidos). [5] Los análogos del teorema de Wagner también se puede extender a la teoría de la matroides : en particular, los mismos dos gráficos K 5 y K 3,3 (junto con otros tres configuraciones prohibidos) aparecen en una caracterización de las matroides gráficos por prohibido matroid menores . [6]
Referencias
- ^ Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Matemáticas. Ana. , 114 : 570–590, doi : 10.1007 / BF01594196 CS1 maint: parámetro desalentado ( enlace ).
- ^ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF) , Fondo. Matemáticas. (en francés), 15 : 271–283 CS1 maint: parámetro desalentado ( enlace ).
- ^ Bondy, JA ; Murty, USR (2008), Teoría de grafos , Textos de posgrado en matemáticas, 244 , Springer, p. 269, ISBN 9781846289699.
- ^ Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society , 43 (1): 75–86, doi : 10.1090 / S0273-0979-05-01088-8 , MR 2188176 CS1 maint: parámetro desalentado ( enlace ).
- ^ Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (5.a ed.), CRC Press, pág. 307, ISBN 9781439826270.
- ^ Seymour, PD (1980), "Sobre la caracterización de Tutte de las matroides gráficas", Annals of Discrete Mathematics , 8 : 83–90, doi : 10.1016 / S0167-5060 (08) 70855-0 , MR 0597159 CS1 maint: parámetro desalentado ( enlace ).