Matematyka dyskretna 1/Wykład 14: Grafy III

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grafy planarne

Graf płaski to para: , gdzie

  • jest jakimś zbiorem punktów płaszczyzny ,
  • jest zbiorem nie przecinających się odcinków lub łuków w o końcach ze zbiorze .

Graf planarny to graf, który jest prezentowalny jako graf płaski.

{grafy_planarne} {Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c) [Rysunek z pliku: grafyplanarne.eps]}

Obserwacja 1

Grafy i nie są planarne.

Dowód

Graf ma sześcio-elementowy cykl Hamiltona . Musi on być narysowany w dowolnej płaskiej prezentacji. Przykładowe umiejscowienie tego cyklu prezentuje rys. Uzupelnic pict k33|.

{grafy_k33} { [Rysunek z pliku: grafyk33.eps]}

Spośród krawędzi i jedna musi leżeć wewnątrz cyklu a druga musi leżeć na zewnątrz. W konsekwencji nie da się narysować krawędzi nie przecinając krawędzi lub .

{grafy_k332} { [Rysunek z pliku: grafyk332.eps]}

Dowód dla jest analogiczny, rozpoczynając od pięcio-elementowego cyklu Hamiltona.

End of proof.gif

Z Obserwacji Uzupelnic th k5 i k33 nieplanarne| natychmiast wynika, że żaden graf zawierający lub nie jest planarny. Ale również graf powstały np. z poprzez umieszczenie na jednej krawędzi dodatkowego wierzchołka nie jest planarny mimo, że nie zawiera podgrafu ani . Dla scharakteryzowania grafów planarnych potrzebne nam będzie następujące pojęcie homeomorficzności grafów.

Graf jest homeomorficzny z grafem , jeśli jeden otrzymamy z drugiego poprzez wykonanie skończenie wielu poniższych operacji:

  • Dodawanie wierzchołków stopnia dwa na krawędzi.
    Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle uw\in{\sf E}\!\left(\mathbf{G}_1\right)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle x\not\in{\sf V}\!\left(\mathbf{G}_1\right)} , to operacja ta zastępuje graf Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle \left( {\sf V}\!\left(\mathbf{G}_1\right),{\sf E}\!\left(\mathbf{G}_1\right) \right)} grafem Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle \left( {\sf V}\!\left(\mathbf{G}_1\right)\cup\left\lbrace x \right\rbrace,{\sf E}\!\left(\mathbf{G}_1\right)\cup\left\lbrace ux,xw \right\rbrace-\left\lbrace uw \right\rbrace \right)} .
  • Usuwanie wierzchołków stopnia dwa.
    Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle x\in{\sf V}\!\left(\mathbf{G}_1\right)} ma jedynie dwóch sąsiadów , to operacja ta zastępuje graf Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle \left( {\sf V}\!\left(\mathbf{G}_1\right),{\sf E}\!\left(\mathbf{G}_1\right) \right)} grafem Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle \left( {\sf V}\!\left(\mathbf{G}_1\right)-\left\lbrace x \right\rbrace,{\sf E}\!\left(\mathbf{G}_1\right)\cup\left\lbrace uw \right\rbrace-\left\lbrace ux,xw \right\rbrace \right)} .

Przykład

Grafy przedstawione na rysunku Uzupelnic pict homeomorficzne| są ze sobą homeomorficzne, zaś nie jest homeomorficzny ani z ani z .

{grafy_homeomorficzne} { [Rysunek z pliku: grafyhomeomorficzne.eps]}

Następne twierdzenie podaje prostą charakteryzację grafów planarnych. Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.

Twierdzenie 2 [Kuratowski 1930]

Graf jest planarny wtedy i tylko wtedy, gdy żaden jego podgraf nie jest homeomorficzny z ani z .

Kolejne charakterystyka grafów planarnych odwołuje się do znanego nam już pojęcia sciągalności, lub grafu ilorazowego. Przypomnijmy, że

  • iloraz grafu przez relację równoważności na zbiorze jego wierzchołków to graf postaci
  • ściągnięcie zbioru wierzchołków w grafie to szczególny przypadek ilorazu , w którym klasy równoważności wszystkich wierzchołków spoza są jednoelementowe, a stanowi dodatkową klasę, tzn. . W ten sposób zbiór został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z . Z drugiej strony, jeśli jest relacją równoważności o klasach , to ściągając w grafie kolejno zbiory otrzymamy graf ilorazowy .

Dowód charakteryzacji grafów planarnych w terminach ściągalności również pomijamy.

Twierdzenie 3

Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu ściągalnego do lub .

Przykład

W grafie przedstawionym na rysunku Uzupelnic pict sciagalny k33| ściągnięcie zbiorów wierzchołków otoczonych przerywaną linią prowadzi do grafu zawierającego . A więc, na mocy Twierdzenia Uzupelnic th ściągalny k5k33|, graf ten nie jest planarny.

{grafy_sciagalny_k33} {Graf posiadający podgraf ściągalny do . [Rysunek z pliku: grafysciagalnyk33.eps]}

W grafach płaskich poza wierzchołkami oraz krawędziami można rozważać również ściany, czyli obszary płaszczyzny otoczone krawędziami.

Ściana w grafie płaskim to spójny obszar płaszczyzny po usunięciu linii reprezentujących krawędzie, tzn. Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle R^2-\bigcup{\sf E}\!\left(\mathbf{G}\right)} . Innym słowy ściana to zbiór punktów płaszczyzny, które da się połączyć krzywą nieprzecinającą żadnej krawędzi.

{grafy_sciany} {Graf posiadający cztery ściany: . [Rysunek z pliku: grafysciany.eps]}

Ściana w grafie z rysunku Uzupelnic pict ściana| jest ścianą nieograniczoną, która nazywana jest też ścianą nieskończoną. Nie tylko ten graf, ale wszystkie grafy płaskie mają dokładnie jedną ścianę nieskończoną. Zauważmy, że las jest grafem planarnym, ale w żadnej reprezentacji płaskiej nie posiada ścian ograniczonych. Tak więc posiada w ogóle tylko jedną ścianę. Tym samym, następne twierdzenie jest uogólnieniem związku między liczbą wierzchołków, krawędzi i drzew (tzn. spójnych składowych) w lesie.

Twierdzenie 4 [Euler 1750]

W grafie płaskim o ścianach i składowych spójnych zachodzi

Dowód

Dowód poprowadzimy indukcją ze względu na liczbę krawędzi. Jeżeli graf jest pusty to , które to wartości spełniają podaną równość. Załóżmy, że . Wybierzmy dowolną krawędź . Jeżeli nie leży na żadnym cyklu grafu , to usunięcie zwiększy o liczbę składowych ale nie zmieni liczby ścian. Tak więc, na mocy założenia indukcyjnego, , co daje żądaną równość. Załóżmy więc, że leży na jakimś cyklu . Tym samym jest granicą pomiędzy dwoma różnymi ścianami, jako że dowolna krzywa przechodząca z jednej strony na drugą stronę granicy wyznaczonej przez krawędź musi przecinać jakąś krawędź z cyklu . Tak więc usunięcie krawędzi zmniejszy liczbę ścian o jeden. Ale teraz usunięcie krawędzi nie zmienia liczby składowych. Założenie indukcyjne daje nam więc , czyli żądaną równość dla grafu .

End of proof.gif
Uwaga

Ważną konsekwencją Twierdzenia Uzupelnic th ilość krawędzi| jest to, że liczba ścian zależy jedynie od liczby wierzchołków, krawędzi, oraz spójnych składowych. Tak więc w każdej reprezentacji płaskiej musi być taka sama.

Uzasadnienie dwu kolejnych wniosków z Twierdzenia Uzupelnic th ilość krawędzi| pozostawiamy jako ćwiczenie.

Wniosek 5

Jeśli jest spójnym grafem planarnym o co najmniej wierzchołkach, to

Wniosek 6

Spójny graf planarny o posiada wierzchołek o stopniu nie większym niż .

Graf dualny geometrycznie do grafu płaskiego to graf płaski skonstruowany w następujący sposób:

  • Z każdej ściany grafu wybieramy po jednym punkcie. Tak wybrane punkty tworzą zbiór wierzchołków .
  • Jeśli krawędź po jednej stronie sąsiadowała ze ścianą , a po drugiej z to w grafie odpowiadające ścianom wierzchołki łączymy krawędzią . Tak wybrane krawędzie tworzą zbiór .

{grafy_dualny} {Graf (w kolorze czarnym) oraz graf do niego dualny geometrycznie (w kolorze turkusowym). [Rysunek z pliku: grafydualny.eps]}

Twierdzenie 7

Jeśli jest spójnym grafem płaskim, to jest izomorficzny z .

Dowód

Każda ściana grafu reprezentowana jest jednym wierzchołkiem . Z drugiej strony, w każdej ścianie grafu znajduje się dokładnie jeden wierzchołek grafu . Ponadto, jeśli wierzchołki grafu są sąsiednie, to ściany grafu zawierające odpowiednio i graniczą ze sobą. To kolei oznacza, że wierzchołki grafu odpowiadające ścianom oraz są sąsiednie. Oczywiście, przy przejściu z do i potem do wierzchołki i przechodzą w . Analogicznie jeżeli jest połączony krawędzią z w , to i również z w .

End of proof.gif

Twierdzenie 8

Niech będzie grafem geometrycznie dualnym do grafu płaskiego . Wtedy podzbiór krawędzi grafu jest cyklem w grafie wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru jest rozcięciem grafu .

Dowód

Niech będzie cyklem w grafie . W grafie płaskim cykl dzieli płaszczyznę na dwie spójne części oraz , przy czym załóżmy, że jest ograniczona przez , a jest nieograniczona. Niech będzie dowolną ścianą we wnętrzu , zaś ścianą nieskończoną, czyli zawartą w a niech będą odpowiadającymi tym ścianom punktami grafu dualnego . Tak więc, , a . A zatem dowolnie wybrana droga z do musi przeciąć cykl co najmniej raz. Przecinające się krawędzie, jedna z drogi i druga z cyklu , są wzajemnie dualne (przy przejściu z do i z powrotem do ). Tak więc, zbiór krawędzi dualnych do krawędzi z cyklu tworzy zbiór rozspajający wierzchołki .

{grafy_cykl_rozc} { [Rysunek z pliku: grafycyklrozc.eps]}

Pokażemy, że zbiór jest rozcięciem, czyli minimalnym zbiorem rozspajającym. Zmniejszenie powstaje oczywiście poprzez zmniejszenie zbioru . Usunięcie jednakże krawędzi z , powoduje połączenie obszaru z obszarem . Pozwala to tworzyć krzywe łączące dowolne dwa punkty i nie przecinające krawędzi ze zbioru . W konsekwencji pozwala to na tworzenie ścieżek między dowolnymi wierzchołkami grafu omijając krawędzie z .

Dowód implikacji w drugą stronę jest analogiczny.

End of proof.gif

Kolorowanie grafów.

W tej części wykładu zajmiemy się problemami związanymi z kolorowaniem grafów. Intuicyjnie kolorowanie to przypisanie wierzchołkom grafu kolorów w taki sposób, by każde dwa sąsiednie wierzchołki miały różne kolory

Kolorowanie grafu to funkcja taka, że ilekroć jest krawędzią grafu .

Kolorowanie grafu na kolorów wyznacza rozbicie zbioru na sumę rozłączną jednobarwnych zbiorów , przy czym każdy graf indukowany postaci jest antykliką. Na odwrót, rozbicie pozwala na pokolorowanie grafu na kolorów.

Graf -kolorowalny (-barwny) to graf dający się pokolorować barwami.

Liczba chromatyczna grafu, , to najmniejsza liczba barw, którymi można pokolorować graf .

Optymalne kolorowanie grafu to kolorowanie używające dokładnie kolorów.

{grafy_kolorowanie} {Kolorowanie grafu nieoptymalne (a), optymalne (b) oraz niepoprawne (c) [Rysunek z pliku: grafykolorowanie.eps]}

Twierdzenie 9

Graf, którego wszystkie wierzchołki mają stopień nie większy niż jest -kolorowalny.

Dowód

Dowód poprowadzimy indykcyjnie ze względu na liczbę wierzchołków w grafie . Jeśli graf ma jeden wierzchołek, to oczywiście wystarcza jeden kolor. Załóżmy więc, że . Wybierzmy dowolny wierzchołek i rozważmy graf . Na mocy założenia indukcyjnego da się go pokolorować barwami. Zauważmy, że ma co najwyżej sąsiadów. Wśród kolorów użytych w kolorowaniu grafu jest więc kolor nie przypisany żadnemu sąsiadowi wierzchołka . Wybieramy więc ten kolor jako barwę dla . Udało się pokolorować graf zbiorem kolorów, co kończy dowód.

End of proof.gif

Ograniczenia górnego, na liczbę chromatyczną grafu, podanego w Twierdzeniu Uzupelnic th rho plus 1| nie można w ogólności wzmocnić. Istotnie, każde kolorowanie kliki wymaga dokładnie kolorów, mimo iż stopień każdego wierzchołka to . Następne twierdzenie wzmacnia jednak znacznie twierdzenia Uzupelnic th rho plus 1|, ale podajemy je bez dowodu.

Twierdzenie 10 [Brooks 1941]

Niech będzie spójnym grafem prostym, który nie jest kliką. Jeśli wszystkie wierzchołki grafu mają stopień nie większy niż i , to jest -kolorowalny.

Oczywiście nie powinno dziwić nas, że dla grafów specjalnego typu można na ogół powiedzieć więcej o ich liczbie chromatycznej.

Obserwacja 11

Graf jest dwudzielny wtedy i tylko wtedy, gdy jest -kolorowalny.

Dowód

Zauważmy najpierw, że w grafie dwudzielnym , podgrafy indukowane oraz są antyklikami. Wystarczy więc pokolorować wierzchołki z jednym kolorem, a wierzchołki z drugim. Z drugiej strony wierzchołki grafu -kolorowalnego daje się oczywiście rozbić na dw zbiory indukujące antykliki, jak tego wymaga dwudzielność.

End of proof.gif

Twierdzenie 12

Każdy graf planarny jest -kolorowalny.

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków w grafie . Dla teza jest oczywista. Niech więc . Z wniosku [[##cn deg v<=5 dla plan|Uzupelnic cn deg v<=5 dla plan|]] wiemy, że ma jakiś wierzchołek o stopniu niewiększym niż . Na mocy założenia indukcyjnego wiemy, że graf jest -kolorowalny. Jeżeli ma mniej niż -ciu sąsiadów, to można go pokolorować kolorem niewystępującym u żadnego sąsiada, co kończyłoby dowód. Podobnie, gdyby jakiś kolor występował u co najmniej dwóch sąsiadów wierzchołka , to także można byłoby zakończyć dowód, gdyż Wśród -ciu kolorów dostępnych do kolorowania grafu jest kolor nie przypisany żadnemu sąsiadowi wierzchołka i może być wobec tego użyty dla . Możemy więc założyć, że ma sąsiadów odpowiednio o kolorach: . Bez straty ogólności ich ułożenie może wyglądać jak na rysunku Uzupelnic pict grafy 5barw planar|.

{grafy_5barw_planar} { [Rysunek z pliku: grafy5barwplanar.eps]}

Niech będzie restrykcją grafu do zbioru wszystkich jego wierzchołków o barwach oraz . Jeśli i nie są w tej samej spójnej składowej grafu , to można zamienić kolory i w spójnej składowej wierzchołka . Tak więc, z racji, że teraz otrzymał kolor , koloru można użyć do pokolorowania wierzchołka . Pozostał przypadek, gdy oraz są w tej samej spójnej składowej grafu . Oznaczy to, że istnieje ścieżka zawarta w i łącząca z . W efekcie otrzymujemy cykl , który ogranicza obszar zawierający wierzchołek i nie zawierający .

{grafy_5barw_planar2} { [Rysunek z pliku: grafy5barwplanar2.eps]}

Z planarności dostajemy więc, że wierzchołki oraz nie mogą być w tej samej spójnej składowej grafu . W takim razie podobnie, jak powyżej możemy podmienić kolory w spójnej składowej wierzchołka tak, że otrzyma kolor . Ale teraz możemy pokolorować wierzchołek na kolor , co kończy dowód.

End of proof.gif

Okazuje się że prawdziwe jest mocniejsze i słynne twierdzenie o czterech barwach. Jego długi i skomplikowany dowód został otrzymany przy użyciu specjalnie napisanego programu do rozważenia bardzo wielu przypadków. Dowód ten pomijamy.

Twierdzenie 13

Każdy graf planarny jest -kolorowalny.

Mapa to graf płaski nie zawierający mostów.

W mapach rozważa się kolorowanie ścian.

Mapa ma -kolorowalne ściany jeśli jej ściany można pokolorować kolorami w ten sposób, by żadne dwie graniczące ze sobą ściany nie miały tego samego koloru. Innymi słowy, mapa ma -kolorowalne ściany, jeśli jej geometrycznie dualny graf jest kolorowalny.

Twierdzenie 14

Mapa ma -kolorowalne ściany wtedy i tylko wtedy, gdy graf jest eulerowski.

Dowód

Załóżmy najpierw, że ściany są pomalowane dwoma kolorami. Wtedy każdy wierzchołek musi być incydentny z parzystą liczbą ścian, a zatem musi mieć parzysty stopień. Na mocy Twierdzenia Eulera otrzymujemy więc, że jest eulerowski.

Niech teraz będzie grafem eulerowskim. Wtedy, na mocy wniosku z Twierdzenia Eulera, jego krawędzie można podzielić na rozłączne krawędziowo cykle . Kolorowanie ścian mapy zdefiniujmy poprzez przypisanie ścianie pierwszego koloru, jeśli jest otoczona nieparzystą liczbą cykli spośród , albo poprzez przypisanie drugiego koloru, jeśli jest otoczona parzystą liczbą cykli. Kolorowanie to jest poprawne, gdyż jeśli dwie ściany graniczą ze sobą poprzez krawędź jakiegoś cyklu , to jedna z tych ścian leży wewnątrz cyklu , a druga na zewnątrz . W stosunku do pozostałych cykli spośród , albo obie ściany są wewnątrz, albo obie na zewnątrz. Tak więc różni je parzystość liczby cykli, we wnętrzu których leżą. Tym samym, w zdefiniowanym kolorowaniu, otrzymają różne kolory.

End of proof.gif

Z Twierdzenia Uzupelnic th 4barw planar|, poprzez przejście od mapy do grafu geometrycznie dualnego dostajemy natychmiast następujący wniosek.

Wniosek 15

Każda mapa ma -kolorowalne ściany.

Z powodu dużego znaczenia kolorowania tak w samej teorii grafów, jak i w algorytmice, problemy kolorowania doczekały się bardzo rozbudowanych pojęć i narzędzi. Poznamy teraz jeszcze jedno z nich.

Liczba stopniowa grafu. Niech będzie grafem prostym. Przy każdej permutacji każdemu wierzchołkowi przypisana jest liczba sąsiadów w zbiorze wierzchołków o indeksie mniejszym niż . Liczba stopniowa jest równa

Przykład

Rozważmy graf przedstawiony na rysunku Uzupelnic grafy liczba stopniowa 1|.

{grafy_liczba_stopniowa_1} {Graf . [Rysunek z pliku: grafyliczbastopniowa1.eps]}

Dla permutacji zadanej przez

mamy i wartość ta jest realizowana przez wierzchołki i . Wierzchołki ułożone w porządku przedstawione są na rysunku Uzupelnic grafy liczba stopniowa 2|.

Przeglądając z kolei wszystkie możliwe permutacje możemy stwierdzić, że nasza permutacja realizuje minimum , a zatem .

{grafy_liczba_stopniowa_2} {Graf z wierzhołkami w porządku wyznaczonym przez . [Rysunek z pliku: grafyliczbastopniowa2.eps]}

Graf można teraz pokolorować następującą procedurą. Wybierając kolejno wierzchołki nadajemy im kolor niewykorzystany dla żadnego dotąd rozpatrywanego sąsiada. Otrzymujemy wtedy kolorowanie przedstawione na rysunku Uzupelnic grafy liczba stopniowa 3|.

{grafy_liczba_stopniowa_3} {Kolorowanie grafu . [Rysunek z pliku: grafyliczbastopniowa3.eps]}

Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.

Obserwacja 16

Jeżeli jest grafem prostym, to

Dowód

Niech będzie ciągiem wierzchołków grafu w porządku realizującym wartość . Wskażemy kolorowanie za pomocą barw. Wierzchołki kolorowane są kolejno zgodnie z ich numeracją. Załóżmy, że pokolorowane zostały już wierzchołki . Wierzchołek ma co najwyżej sąsiadów w zbiorze , tak więc w zbiorze kolorów jest jeszcze co najmniej jeden kolor nie wykorzystany dla tych wcześniejszych sąsiadów . Przydzielamy go więc wierzchołkowi . Czynność ta jest powtarzana, aż do momentu pokolorowania wszystkich wierzchołków w Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle {\sf V}\!\left(\mathbf{G}\right)} .

End of proof.gif