Twierdzenie Kuratowskiego

Podział K _3,3 w uogólnionym grafie Petersena G (9,2), pokazujący, że graf jest niepłaski.

W teorii grafów twierdzenie Kuratowskiego jest matematycznie zakazaną charakterystyką grafów planarnych , nazwaną na cześć Kazimierza Kuratowskiego . Stwierdza, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu, który jest podpodziałem ( pełny wykres na pięciu wierzchołkach $)$ lub $Displaystyle K_{3,3}}$ ( kompletny graf dwudzielny na sześciu wierzchołkach, z których trzy łączą się z każdym z pozostałych trzech, znany również jako wykres użyteczności ).

Oświadczenie

Graf planarny to graf, którego wierzchołki mogą być reprezentowane przez punkty na płaszczyźnie euklidesowej , a krawędzie mogą być reprezentowane przez proste krzywe na tej samej płaszczyźnie łączące punkty reprezentujące ich punkty końcowe, tak że żadne dwie krzywe nie przecinają się poza wspólnym punktem końcowym. Wykresy planarne są często rysowane za pomocą odcinków linii prostych reprezentujących ich krawędzie, ale zgodnie z twierdzeniem Fáry'ego nie ma to wpływu na ich charakterystykę teoretyczną.

Podział grafu to graf utworzony przez podzielenie jego krawędzi na ścieżki jednej lub więcej krawędzi . Twierdzenie Kuratowskiego stwierdza, że graf skończony $jest$ $,$ ${\ Displaystyle K_ {3,3}$ nie można podzielić krawędzi lub , a następnie ewentualnie dodać dodatkowe krawędzie i wierzchołki, aby utworzyć wykres izomorficzny z ${\ displaystyle G}$ . Równoważnie skończony graf $jest planarny wtedy i tylko wtedy$ ${\ Displaystyle K_ {3,3}$ gdy nie zawiera podgrafu, który jest homeomorficzny z lub .

Podgrafy Kuratowskiego

Dowód bez słów , że graf hipersześcianu jest niepłaski , używając twierdzeń Kuratowskiego lub Wagnera i znajdując podgrafy K ₅ (na górze) lub K _3,3 (na dole)

Jeśli $jest$ wykresem zawierającym podgraf , który jest podpodziałem lub $Displaystyle$ $K_ {5}}$ lub $\ Displaystyle K_ {3,3}}$ , to jest znany jako podgraf Kuratowskiego z $G}$ $displaystyle$ . Za pomocą tego zapisu twierdzenie Kuratowskiego można wyrazić zwięźle: graf jest planarny wtedy i tylko wtedy, gdy nie ma podgrafu Kuratowskiego.

Dwa wykresy i $K_$ $3,3}}$ { są niepłaskie, co można wykazać za pomocą przypadku lub argumentu dotyczącego wzoru Eulera Ponadto podział wykresu nie może zamienić wykresu nieplanarnego w wykres planarny: jeśli podział wykresu $G$ płaski rysunek, ścieżki podziału tworzą krzywe, które mogą być użyte do przedstawienia krawędzi sol {\ $} \displaystyle G}$ samo. Dlatego graf zawierający podgraf Kuratowskiego nie może być planarny. Trudniejszym kierunkiem w udowodnieniu twierdzenia Kuratowskiego jest wykazanie, że jeśli graf jest niepłaski, to musi zawierać podgraf Kuratowskiego.

Implikacje algorytmiczne

Podgraf Kuratowskiego grafu niepłaskiego można znaleźć w czasie liniowym , mierzonym rozmiarem grafu wejściowego. Pozwala to zweryfikować poprawność testowania planarności dla wejść nieplanarnych, ponieważ łatwo jest sprawdzić, czy dany podgraf jest, czy nie jest podgrafem Kuratowskiego. Zwykle grafy nieplanarne zawierają dużą liczbę podgrafów Kuratowskiego. Ekstrakcja tych podgrafów jest potrzebna np. w rozgałęzień i cięć do minimalizacji przecinania. Możliwe jest wyodrębnienie dużej liczby podgrafów Kuratowskiego w czasie zależnym od ich całkowitej wielkości.

Historia

Kazimierz Kuratowski opublikował swoje twierdzenie w 1930 r. Twierdzenie zostało niezależnie udowodnione przez Orrina Frinka i Paula Smitha również w 1930 r., ale ich dowód nigdy nie został opublikowany. Szczególny przypadek sześciennych grafów planarnych (dla których jedynym minimalnym zakazanym podgrafem jest ) został również niezależnie udowodniony przez Karla Mengera w 1930 r. Od tego czasu kilka nowych dowodów twierdzenia ${\ displaystyle K_ {3,3}}}$ zostały odkryte.

W Związku Radzieckim twierdzenie Kuratowskiego było znane jako twierdzenie Pontriagina-Kuratowskiego lub twierdzenie Kuratowskiego-Pontryagina , ponieważ twierdzenie to zostało podobno udowodnione niezależnie przez Lwa Pontriagina około 1927 r. Ponieważ jednak Pontriagin nigdy nie opublikował swojego dowodu, to użycie nie rozprzestrzeniło się do innych miejsc.

Powiązane wyniki

Ściśle powiązany wynik, $\ Displaystyle K_ {3,3}}$ Wagnera , grafy planarne według ich nieletnich w kategoriach tych samych dwóch zakazanych grafów $i$ K . Każdy podgraf Kuratowskiego jest szczególnym przypadkiem minora tego samego typu i chociaż sytuacja odwrotna nie jest prawdziwa, nietrudno jest znaleźć podgraf Kuratowskiego (tego czy innego typu) od jednego z tych dwóch zabronionych minorów; dlatego te dwa twierdzenia są równoważne.

Rozszerzeniem jest twierdzenie Robertsona-Seymoura .

Zobacz też

Hipoteza Kelmansa – Seymoura , że grafy nieplanarne z 5 połączonymi grafami zawierają podpodział ${\ Displaystyle K_ {5}}$