Twierdzenie o strukturze grafów

W matematyce twierdzenie o strukturze grafów jest głównym wynikiem w dziedzinie teorii grafów . Wynik ustanawia głęboki i fundamentalny związek między teorią drugorzędnych grafów a osadzeniem topologicznym . Twierdzenie to jest przedstawione w siedemnastym z serii 23 artykułów autorstwa Neila Robertsona i Paula Seymoura . Jego dowód jest bardzo długi i skomplikowany. Kawarabayashi i Mohar (2007) i Lovász (2006) to ankiety dostępne dla niespecjalistów, opisujące twierdzenie i jego konsekwencje.

Konfiguracja i motywacja twierdzenia

Drugorzędny grafu G to dowolny graf H , który jest izomorficzny z grafem, który można otrzymać z podgrafu G przez skrócenie niektórych krawędzi. Jeśli G nie ma grafu H jako drugorzędnego, to mówimy, że G jest H -wolny . Niech H będzie grafem ustalonym. Intuicyjnie, jeśli G jest dużym H -free graph, to powinien być ku temu „dobry powód”. Twierdzenie o strukturze grafu dostarcza takiego „dobrego powodu” w postaci przybliżonego opisu struktury G . W istocie każdy graf G wolny od H ma jedną z dwóch wad strukturalnych: albo G jest „zbyt cienki”, aby mieć H jako drugorzędny, albo G może być (prawie) topologicznie osadzony na powierzchni, która jest zbyt prosta, aby osadzić H od. Pierwszy powód ma zastosowanie, jeśli H jest grafem planarnym , i oba powody mają zastosowanie, jeśli H nie jest planarne. Najpierw uściślimy te pojęcia.

Szerokość drzewa

Szerokość drzewa wykresu G jest dodatnią liczbą całkowitą, która określa „cienkość” G . Na przykład spójny graf G ma szerokość drzewa jeden wtedy i tylko wtedy, gdy jest drzewem, a G ma szerokość drzewa dwa wtedy i tylko wtedy, gdy jest grafem szeregowo-równoległym . Intuicyjnie, ogromny graf G ma małą szerokość drzewa wtedy i tylko wtedy, gdy G przyjmuje strukturę ogromnego drzewa, którego węzły i krawędzie zostały zastąpione małymi grafami. Dokładną definicję szerokości drzewa podajemy w podrozdziale dotyczącym sum klików. Jest to twierdzenie, że jeśli H jest nieletnim G , to szerokość drzewa H nie jest większa niż szerokość G . Dlatego jednym „dobrym powodem”, dla którego G jest wolny od H , jest to, że szerokość drzewa G nie jest bardzo duża. Twierdzenie o strukturze wykresu implikuje, że ten powód ma zastosowanie zawsze w przypadku, gdy H jest planarny.

Wniosek 1. Dla każdego grafu planarnego H istnieje dodatnia liczba całkowita k taka, że ​​każdy graf wolny od H ma szerokość drzewa mniejszą niż k .

Szkoda, że ​​wartość k we Wniosku 1 jest na ogół znacznie większa niż szerokość drzewa H (godnym uwagi wyjątkiem jest sytuacja, gdy H = K 4 , pełny graf na czterech wierzchołkach, dla którego k = 3 ). Jest to jeden z powodów, dla których mówi się, że twierdzenie o strukturze grafów opisuje „zgrubną strukturę” grafów wolnych od H.

Osady powierzchniowe

Z grubsza powierzchnia jest zbiorem punktów z lokalną strukturą topologiczną dysku. Powierzchnie dzielą się na dwie nieskończone rodziny: orientowalne obejmują kulę , torus , podwójny torus i tak dalej; powierzchnie nieorientowalne obejmują rzeczywistą płaszczyznę rzutową , butelkę Kleina i tak dalej. Wykres jest osadzony na powierzchni, jeśli wykres można narysować na powierzchni jako zbiór punktów (wierzchołków) i łuków (krawędzi), które nie przecinają się ani nie stykają ze sobą, z wyjątkiem sytuacji, gdy krawędzie i wierzchołki zachodzą na siebie lub przylegają. Graf jest planarny , jeśli jest osadzony na kuli. Jeśli graf G jest osadzony na określonej powierzchni, to każdy drugorzędny G jest również osadzony na tej samej powierzchni. Dlatego „dobrym powodem”, dla którego G jest wolny od H , jest to, że G osadza się na powierzchni, na której H nie jest osadzony.

Gdy H nie jest planarne, twierdzenie o strukturze grafu można traktować jako rozległe uogólnienie twierdzenia Kuratowskiego. Wersja tego twierdzenia udowodniona przez Wagnera (1937) stwierdza, że ​​jeśli graf G jest wolny zarówno od K 5 , jak i od K 3,3 , to G jest planarny. Twierdzenie to dostarcza „dobrego powodu”, aby graf G nie miał K 5 lub K 3,3 jako drugorzędnych; w szczególności G osadza się na kuli, podczas gdy żadne K 5 ani K 3,3 osadzić na kuli. Niestety, to pojęcie „dobrego powodu” nie jest wystarczająco wyrafinowane dla twierdzenia o strukturze grafu. Potrzebne są jeszcze dwa pojęcia: sumy klik i wiry .

Sumy kliki

Klika w grafie G to dowolny zbiór wierzchołków sąsiadujących ze sobą parami w grafie G . Dla nieujemnej liczby całkowitej k , k -klika-suma dwóch grafów G i K to dowolny wykres otrzymany przez wybranie nieujemnej liczby całkowitej m ≤ k , wybranie kliki o rozmiarze m w każdym z G i K , identyfikujące dwa kliki w jedną klikę wielkości m , a następnie usuwając zero lub więcej krawędzi łączących wierzchołki nowej kliki.

Jeśli G 1 , G 2 , …, G n jest listą grafów, to możemy utworzyć nowy graf, łącząc listę grafów przez k -klika-sum . Oznacza to, że bierzemy k -klikę-sum G 1 i G 2 , następnie bierzemy k -klikę-sumę G 3 z wynikowym wykresem i tak dalej. Wykres ma szerokość drzewa co najwyżej k , jeśli można go uzyskać za pomocą k -sumy-kliki z listy grafów, gdzie każdy graf na liście ma co najwyżej k + 1 wierzchołków.

Wniosek 1 wskazuje nam, że sumy k -kliki małych grafów opisują zgrubną strukturę grafów wolnych od H , gdy H jest planarne. Gdy H jest niepłaskie, musimy również wziąć pod uwagę k -kliki-sum listy grafów, z których każdy jest osadzony na powierzchni. Poniższy przykład z H = K 5 ilustruje ten punkt. Wykres K 5 jest osadzony na każdej powierzchni z wyjątkiem kuli. Jednak istnieje K 5 -wolne grafy, które są dalekie od planarnych. W szczególności suma 3 klik dowolnej listy grafów planarnych daje od K5 . Wagner (1937) określił dokładną strukturę grafów wolnych od K 5 jako część grupy wyników znanej jako twierdzenie Wagnera :

Twierdzenie 2. Jeśli G jest wolne od K 5 , to G można otrzymać za pomocą 3-klikowych sum z listy grafów planarnych i kopii jednego specjalnego nieplanarnego grafu mającego 8 wierzchołków.

Zwracamy uwagę, że Twierdzenie 2 jest twierdzeniem o strukturze dokładnej , ponieważ określona jest dokładna struktura grafów wolnych od K 5 . Takie wyniki są rzadkością w teorii grafów. Twierdzenie o strukturze grafów nie jest w tym sensie precyzyjne, ponieważ dla większości grafów H opis strukturalny grafów wolnych od H zawiera pewne grafy, które nie są wolne od H.

Wiry (zgrubny opis)

Można pokusić się o przypuszczenie, że odpowiednik Twierdzenia 2 zachodzi dla grafów H innych niż K 5 . Być może prawdą jest, że: dla dowolnego niepłaskiego grafu H istnieje dodatnia liczba całkowita k taka, że ​​każdy graf wolny od H można otrzymać za pomocą sum k -kliki z listy grafów, z których każdy ma co najwyżej k wierzchołki lub osadzone na jakiejś powierzchni, na której H nie jest osadzone . Niestety, to stwierdzenie nie jest jeszcze wystarczająco wyrafinowane, aby mogło być prawdziwe. Musimy pozwolić każdemu osadzonemu grafowi G i „oszukiwać” na dwa ograniczone sposoby. Po pierwsze, musimy zezwolić na ograniczoną liczbę miejsc na powierzchni, w których możemy dodać nowe wierzchołki i krawędzie, które mogą się przecinać w sposób o ograniczonej złożoności . Takie miejsca nazywane są wirami . „Złożoność” wiru jest ograniczona parametrem zwanym jego głębokością , ściśle związanym z szerokością ścieżki . Czytelnik może preferować odroczenie czytania następującego dokładnego opisu wiru o głębokości k . Po drugie, musimy zezwolić na dodanie ograniczonej liczby nowych wierzchołków do każdego z osadzonych grafów z wirami.

Wiry (dokładna definicja)

Ściana osadzonego wykresu to otwarta 2-komórkowa powierzchnia, która jest rozłączna z wykresem, ale której granicą jest suma niektórych krawędzi osadzonego wykresu . Niech F będzie ścianą osadzonego grafu G i niech 0 v , v 1 , ..., v n – 1 , v n = v 0 będą wierzchołkami leżącymi na granicy F (w tym porządku kołowym). Przedział kołowy dla F to zbiór wierzchołków postaci { v a , v a +1 , …, v a + s } gdzie a i s są liczbami całkowitymi i gdzie indeksy dolne są zredukowane modulo n . Niech Λ będzie skończoną listą przedziałów kołowych dla F . Konstruujemy nowy graf w następujący sposób. Dla każdego przedziału kołowego L w Λ dodajemy nowy wierzchołek v L , który łączy się z zerem lub większą liczbą wierzchołków w L . Na koniec dla każdej pary { L , M } przedziałów w Λ możemy dodać krawędź łączącą v L z v M pod warunkiem, że L i M mają niepuste przecięcia. O otrzymanym grafie mówi się, że otrzymuje się z G przez dodanie wiru o głębokości co najwyżej k (do ściany F ) pod warunkiem, że żaden wierzchołek na granicy F nie pojawia się w więcej niż k przedziałach w Λ .

Sformułowanie twierdzenia o strukturze grafu

Twierdzenie o strukturze grafów. Dla dowolnego wykresu H istnieje dodatnia liczba całkowita k taka, że ​​każdy wykres wolny od H można otrzymać w następujący sposób:

  1. Zaczynamy od listy wykresów, gdzie każdy wykres na liście jest osadzony na powierzchni, na której H nie jest osadzony
  2. do każdego osadzonego wykresu na liście dodajemy co najwyżej k wirów, gdzie każdy wir ma głębokość co najwyżej k
  3. do każdego wynikowego grafu dodajemy co najwyżej k nowych wierzchołków (nazywanych wierzchołkami ) i dodajemy dowolną liczbę krawędzi, z których każda ma co najmniej jeden punkt końcowy wśród wierzchołków.
  4. na koniec łączymy się poprzez k -clique-sums z wynikającą listą grafów.

Zauważ, że kroki 1. i 2. dają pusty graf, jeśli H jest płaski, ale ograniczona liczba wierzchołków dodana w kroku 3. sprawia, że ​​stwierdzenie jest zgodne z Wnioskiem 1.

Udoskonalenia

Wzmocnione wersje twierdzenia o strukturze grafu są możliwe w zależności od zbioru H zabronionych nieletnich. Na przykład, gdy jeden z grafów w H jest planarny , to każdy graf wolny od H -moll ma dekompozycję drzewa o ograniczonej szerokości; równoważnie można to przedstawić jako sumę klików grafów o stałym rozmiarze. Gdy jeden z wykresów w H można narysować na płaszczyźnie tylko z jednym przecięciem , to H -grafy bez drugorzędnych dopuszczają dekompozycję jako klik-sum grafów o stałym rozmiarze i grafów rodzaju ograniczonego, bez wirów. Inne wzmocnienie jest również znane, gdy jeden z wykresów w H jest wykresem wierzchołkowym .

Zobacz też

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Graph_structure_theorem&oldid=1136252449 ”