En teoria de grafos, la teorema de Wagner és una caracterisació de grafos prohibits en grafos plans, cridat aixina per Klaus Wagner. La teorema establix que un grafo finit és pla si i solament si els seus menors no inclouen a K5 (el grafo complet en cinc vèrtiços) ni a K3,3 (el grafo del problema dels tres servicis, un grafo bipartito complet en sis vèrtiços). Est va ser un dels primers resultats en la teoria de menors i pot vore's com un precursor del teorema de Robertson-Seymour.

K5 (esquerra) i K3,3 (dreta) com a menors del grafo de Petersen no pla (menuts círculs de colors i vores negres sòlides). Els menors es poden formar eliminant el vèrtiç roig i contraent les vores dins de cada círcul groc.
Una suma de cliques de dos grafos plans i el grafo de Wagner, formant un grafo lliure de K5

Definicions i enunciat

Un embebido pla d'un grafo donat és un dibuix del grafo en l'espai bidimensional, en punts per als seus vèrtiços i curves per a les seues arestes, de tal forma que les úniques interseccions entre parells d'arestes són en un punt final comú de les dos arestes. Un menor d'un grafo donat és un atre grafo format en eliminar vèrtiços, eliminar arestes i contraure arestes. Quan es contrau una aresta, els seus dos extrems es fusionen per a formar un sol vèrtiç. En algunes versions de la teoria de grafos menors, el grafo resultant d'una contracció se simplifica en eliminar els bucles propis i les adyacencias múltiples, mentres que en atres versions es permeten multigrafos, pero esta variació no implica cap diferència sobre la teorema de Wagner.

La teorema establix que tot grafo té una incrustació plana o un menor d'un de dos tipos, el grafo complet K5 o el grafo bipartito complete K3,3 (també és possible que un sol grafo tinga abdós tipos de menors).

Si un grafo donat és pla, també ho són tots els seus menors: l'eliminació de vèrtiços i vores òbviament preserva la planaridad, i la contracció de les vores també es pot fer d'una manera que preserve la planaridad, deixant un dels dos punts finals de la vora contreta en el seu lloc i enrutando totes les vores que incidixen en l'atre extrem en la ruta de la vora contreta.

Un grafo no pla menor-mínim és un grafo que no és pla, pero en el que tots els menors propis (menors formats per a lo manco una eliminació o contracció) són plans. Una atra forma d'enunciar la teorema de Wagner és que solament hi ha dos grafos no plans menors-mínims, K5 i K3,3.

Un atre resultat també conegut a voltes com a teorema de Wagner establix que un grafo 4-vèrtiços-conectadp és pla si i solament si no té K5 com a menor. És dir, en assumir un major nivell de conectivitat, es pot fer innecessari el grafo K3,3 en la caracterisació, quedant solament un únic menor prohibit, K5. Correspondientemente, la conjectura de Kelmans-Seymour establix que un grafo 5-conectat és pla si i solament si no té K5 com menor.

Història i relació en la teorema de Kuratowski

 
Existix una demostració sense paraules de que un grafo hipercúbico és no-pla usant el teorema de Kuratowski o la teorema de Wagner; per a trobar els subgrafos K5 (dalt) o be K3,3 (avall)


Wagner va publicar abdós teoremes en 1937,[1] posteriorment a la publicació en 1930 del teorema de Kuratowski,[2] segons el qual un grafo és pla si i solament si no conté com subgrafo una subdivisió d'un dels mateixos dos grafos prohibits K5 i K3,3. En cert sentit, la teorema de Kuratowski és més forta que la teorema de Wagner: una subdivisió es pot convertir en una subdivisió menor del mateix tipo contraent tots menys un de les vores en cada camí format pel procés de subdivisió, pero convertint una subdivisió menor en una subdivisió del mateix tipo no sempre és possible. No obstant, en el cas dels dos grafos K5 i K3,3, és senzill demostrar que un grafo que té a lo manco un d'estos dos grafos com a menor també té a lo manco un d'ells com una subdivisió, per lo que les dos teoremes són equivalents.[3]

Referències

  1. ↑ Wagner, K.(1937).«Über eine Eigenschaft der ebenen Komplexe».Math. Ann..114: 570–590.doi:10.1007/BF01594196..
  2. ↑ Kuratowski, Kazimierz(1930).«Sur li problème dones courbes gauches en topologie».Fund. Math..15: 271–283.(en francés).
  3. ↑ Bondy, J. A.; Murty, U.S.R.(2008).«Graph Theory».Springer.244: 269..


Referències