Matematyka dyskretna 1/Wykład 14: Grafy III

Grafy planarne

Graf płaski to para: $\mathbf {\overline {G}} =\left({\overline {V}},{\overline {E}}\right)$, gdzie

• ${\overline {V}}$ jest jakimś zbiorem punktów płaszczyzny $\mathbb {R} ^{2}$,
• ${\overline {E}}$ jest zbiorem nie przecinających się odcinków lub łuków w $R^{2}$

o końcach ze zbiorze ${\overline {V}}$.

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 ${\mathcal {K}}_{5}$ i ${\mathcal {K}}_{3,3}$ nie są planarne.

Dowód

Graf ${\mathcal {K}}_{3,3}$ ma sześcio-elementowy cykl Hamiltona $H$. 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 $v_{1}v_{4}$ i $v_{2}v_{5}$ jedna musi leżeć wewnątrz cyklu a druga musi leżeć na zewnątrz. W konsekwencji nie da się narysować krawędzi $v_{3}v_{0}$ nie przecinając krawędzi $v_{1}v_{4}$ lub $v_{2}v_{5}$.

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

Dowód dla ${\mathcal {K}}_{5}$ jest analogiczny, rozpoczynając od pięcio-elementowego cyklu Hamiltona.

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

Graf $\mathbf {G} _{1}$ jest homeomorficzny z grafem $\mathbf {G} _{2}$, 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 $u,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 $\mathbf {G} ,\mathbf {G} '$ przedstawione na rysunku Uzupelnic pict homeomorficzne| są ze sobą homeomorficzne, zaś $\mathbf {G} ''$ nie jest homeomorficzny ani z $\mathbf {G}$ ani z $\mathbf {G} '$.

{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 ${\mathcal {K}}_{5}$ ani z ${\mathcal {K}}_{3,3}$.

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

• iloraz grafu $\mathbf {G}$ przez relację równoważności $\theta \subseteq V\times V$ na zbiorze jego wierzchołków to graf postaci $\mathbf {G} /\theta =\left(V/\theta ,\left\lbrace \left\lbrace v/\theta ,w/\theta \right\rbrace :\left\lbrace v,w\right\rbrace \in E\right\rbrace \right),$
• ściągnięcie zbioru wierzchołków $X\subseteq V$ w grafie $\mathbf {G}$ to szczególny przypadek ilorazu $\mathbf {G} /\theta$, w którym klasy równoważności wszystkich wierzchołków spoza $X$ są jednoelementowe, a $X$ stanowi dodatkową klasę, tzn. $V/\theta =\left\lbrace \left\lbrace v\right\rbrace :v\in V-X\right\rbrace \cup \left\lbrace X\right\rbrace$. W ten sposób zbiór $X$ został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z $X$. Z drugiej strony, jeśli $\theta \subseteq V\times V$ jest relacją równoważności o klasach $X_{1},\ldots ,X_{k}$, to ściągając w grafie $\mathbf {G}$ kolejno zbiory $X_{1},\ldots ,X_{k}$ otrzymamy graf ilorazowy $\mathbf {G} /\theta$.

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 ${\mathcal {K}}_{5}$ lub ${\mathcal {K}}_{3,3}$.

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 ${\mathcal {K}}_{3,3}$. 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 ${\mathcal {K}}_{3,3}$. [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 $\mathbf {G}$ 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: $f_{0},f_{1},f_{2},f_{3}$. [Rysunek z pliku: grafysciany.eps]}

Ściana $f_{0}$ 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 $\left\vert E\right\vert =\left\vert V\right\vert -k$ 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 $\mathbf {G} =\left(V,E\right)$ o $f$ ścianach i $k\geq 1$ składowych spójnych zachodzi

$\left\vert V\right\vert -\left\vert E\right\vert +f=k+1.$

Dowód

Dowód poprowadzimy indukcją ze względu na liczbę krawędzi. Jeżeli graf $\mathbf {G}$ jest pusty to $\left\vert E\right\vert =0,k=\left\vert V\right\vert ,\ f=1$, które to wartości spełniają podaną równość. Załóżmy, że $\left\vert E\right\vert >1$. Wybierzmy dowolną krawędź $uv\in E$. Jeżeli $uv$ nie leży na żadnym cyklu grafu $\mathbf {G}$, to usunięcie $uv$ zwiększy o $1$ liczbę składowych ale nie zmieni liczby ścian. Tak więc, na mocy założenia indukcyjnego, $\left\vert V\right\vert -(\left\vert E\right\vert -1)+f=(k+1)+1$, co daje żądaną równość. Załóżmy więc, że $uv$ leży na jakimś cyklu $C$. Tym samym $uv$ 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ź $uv$ musi przecinać jakąś krawędź z cyklu $C$. Tak więc usunięcie krawędzi $uv$ zmniejszy liczbę ścian o jeden. Ale teraz usunięcie krawędzi $uv$ nie zmienia liczby składowych. Założenie indukcyjne daje nam więc $\left\vert V\right\vert -(\left\vert E\right\vert -1)+(f-1)=k+1$, czyli żądaną równość dla grafu $\mathbf {G}$.

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 $\mathbf {G} =\left(V,E\right)$ jest spójnym grafem planarnym o co najmniej $3$ wierzchołkach, to

$\left\vert E\right\vert \leq 3\left\vert V\right\vert -6.$

Wniosek 6

Spójny graf planarny o $\left\vert V\right\vert \geq 1$ posiada wierzchołek o stopniu nie większym niż $5$.

Graf dualny geometrycznie do grafu płaskiego $\mathbf {G} =\left(V,E\right)$ to graf płaski $\mathbf {G} ^{*}=\left(V^{*},E^{*}\right)$ skonstruowany w następujący sposób:

• Z każdej ściany grafu $\mathbf {G}$ wybieramy po jednym punkcie. Tak wybrane punkty tworzą zbiór wierzchołków $V^{*}$.
• Jeśli krawędź po jednej stronie sąsiadowała ze ścianą $f_{1}$, a po drugiej z $f_{2}$ to w grafie $\mathbf {G} ^{*}$ odpowiadające ścianom $f_{1},f_{2}$ wierzchołki $v_{1}^{*},v_{2}^{*}$ łączymy krawędzią $v_{1}^{*}v_{2}^{*}$. Tak wybrane krawędzie tworzą zbiór $E^{*}$.

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

Twierdzenie 7

Jeśli $\mathbf {G}$ jest spójnym grafem płaskim, to $\mathbf {G} ^{**}$ jest izomorficzny z $\mathbf {G}$.

Dowód

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

Twierdzenie 8

Niech $\mathbf {G} ^{*}$ będzie grafem geometrycznie dualnym do grafu płaskiego $\mathbf {G}$. Wtedy podzbiór $C$ krawędzi grafu $\mathbf {G}$ jest cyklem w grafie $\mathbf {G}$ wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru $C$ jest rozcięciem grafu $\mathbf {G} ^{*}$.

Dowód

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

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

Pokażemy, że zbiór $C^{*}$ jest rozcięciem, czyli minimalnym zbiorem rozspajającym. Zmniejszenie $C^{*}$ powstaje oczywiście poprzez zmniejszenie zbioru $C$. Usunięcie jednakże krawędzi $e$ z $C$, powoduje połączenie obszaru $A_{1}$ z obszarem $A_{0}$. Pozwala to tworzyć krzywe łączące dowolne dwa punkty $A_{0}\cup A_{1}$ i nie przecinające krawędzi ze zbioru $C-\left\lbrace e\right\rbrace$. W konsekwencji pozwala to na tworzenie ścieżek między dowolnymi wierzchołkami grafu $\mathbf {G} ^{*}$ omijając krawędzie z $C-\left\lbrace e\right\rbrace$.

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

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 $\mathbf {G} =\left(V,E\right)$ to funkcja $c:V\longrightarrow \mathbb {N}$ taka, że $c(v)\neq c(w)$ ilekroć $vw$ jest krawędzią grafu $\mathbf {G}$.

Kolorowanie grafu $\mathbf {G}$ na $k$ kolorów wyznacza rozbicie zbioru $V$ na sumę rozłączną $V=V_{0}\cup V_{1}\cup \ldots \cup V_{k-1}$ jednobarwnych zbiorów $V_{i}$, przy czym każdy graf indukowany postaci $\mathbf {G} |_{V_{i}}$ jest antykliką. Na odwrót, rozbicie $V=V_{0}\cup V_{1}\cup \ldots \cup V_{k-1}$ pozwala na pokolorowanie grafu $\mathbf {G}$ na $k$ kolorów.

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

Liczba chromatyczna grafu, $\chi \!\left(\mathbf {G} \right)$, to najmniejsza liczba barw, którymi można pokolorować graf $\mathbf {G}$.

Optymalne kolorowanie grafu $\mathbf {G}$ to kolorowanie używające dokładnie $\chi \!\left(\mathbf {G} \right)$ 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ż $k$ jest $(k+1)$-kolorowalny.

Dowód

Dowód poprowadzimy indykcyjnie ze względu na liczbę wierzchołków w grafie $\mathbf {G} =\left(V,E\right)$. Jeśli graf ma jeden wierzchołek, to oczywiście wystarcza jeden kolor. Załóżmy więc, że $\left\vert V\right\vert \geq 2$. Wybierzmy dowolny wierzchołek $v\in V$ i rozważmy graf $\mathbf {G} |_{V-\left\lbrace v\right\rbrace }$. Na mocy założenia indukcyjnego da się go pokolorować $k+1$ barwami. Zauważmy, że $v$ ma co najwyżej $k$ sąsiadów. Wśród $k+1$ kolorów użytych w kolorowaniu grafu $\mathbf {G} |_{V-\left\lbrace x\right\rbrace }$ jest więc kolor nie przypisany żadnemu sąsiadowi wierzchołka $v$. Wybieramy więc ten kolor jako barwę dla $v$. Udało się pokolorować graf $\mathbf {G}$ zbiorem $k+1$ kolorów, co kończy dowód.

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 ${\mathcal {K}}_{k+1}$ wymaga dokładnie $k+1$ kolorów, mimo iż stopień każdego wierzchołka to $k$. Następne twierdzenie wzmacnia jednak znacznie twierdzenia Uzupelnic th rho plus 1|, ale podajemy je bez dowodu.

Twierdzenie 10 [Brooks 1941]

Niech $\mathbf {G}$ będzie spójnym grafem prostym, który nie jest kliką. Jeśli wszystkie wierzchołki grafu $\mathbf {G}$ mają stopień nie większy niż $k$ i $k\geq 3$, to $\mathbf {G}$ jest $\rho$-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 $2$-kolorowalny.

Dowód

Zauważmy najpierw, że w grafie dwudzielnym $\mathbf {G} =\left(V_{1}\cup V_{2},E\right)$, podgrafy indukowane $\mathbf {G} |_{V_{1}}$ oraz $\mathbf {G} |_{V_{2}}$ są antyklikami. Wystarczy więc pokolorować wierzchołki z $V_{1}$ jednym kolorem, a wierzchołki z $V_{2}$ drugim. Z drugiej strony wierzchołki grafu $2$-kolorowalnego daje się oczywiście rozbić na dw zbiory indukujące antykliki, jak tego wymaga dwudzielność.

Twierdzenie 12

Każdy graf planarny jest $5$-kolorowalny.

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków w grafie $\mathbf {G} =\left(V,E\right)$. Dla $\left\vert V\right\vert =1$ teza jest oczywista. Niech więc $\left\vert V\right\vert \geq 2$. Z wniosku [[##cn deg v<=5 dla plan|Uzupelnic cn deg v<=5 dla plan|]] wiemy, że $\mathbf {G}$ ma jakiś wierzchołek $v$ o stopniu niewiększym niż $5$. Na mocy założenia indukcyjnego wiemy, że graf $\mathbf {G} |_{V-\left\lbrace v\right\rbrace }$ jest $5$-kolorowalny. Jeżeli $v$ ma mniej niż $5$-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 $v$, to także można byłoby zakończyć dowód, gdyż Wśród $5$-ciu kolorów dostępnych do kolorowania grafu $\mathbf {G}$ jest kolor nie przypisany żadnemu sąsiadowi wierzchołka $v$ i może być wobec tego użyty dla $v$. Możemy więc założyć, że $v$ ma $5$ sąsiadów $v_{1},v_{2},v_{3},v_{4},v_{5}$ odpowiednio o kolorach: $1,2,3,4,5$. 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 $\mathbf {P} _{i,j}$ będzie restrykcją grafu $\mathbf {G}$ do zbioru wszystkich jego wierzchołków o barwach $i$ oraz $j$. Jeśli $v_{1}$ i $v_{3}$ nie są w tej samej spójnej składowej grafu $\mathbf {P} _{1,3}$, to można zamienić kolory $1$ i $3$ w spójnej składowej wierzchołka $v_{1}$. Tak więc, z racji, że teraz $v_{1}$ otrzymał kolor $3$, koloru $1$ można użyć do pokolorowania wierzchołka $v$. Pozostał przypadek, gdy $v_{1}$ oraz $v_{3}$ są w tej samej spójnej składowej grafu $\mathbf {P} _{1,3}$. Oznaczy to, że istnieje ścieżka $R$ zawarta w $\mathbf {P} _{1,3}$ i łącząca $v_{1}$ z $v_{3}$. W efekcie otrzymujemy cykl $v\to v_{1}\to R\to v_{3}\to v$, który ogranicza obszar zawierający wierzchołek $v_{2}$ i nie zawierający $v_{4}$.

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

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

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 $4$-kolorowalny.

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

W mapach rozważa się kolorowanie ścian.

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

Twierdzenie 14

Mapa $\mathbf {M}$ ma $2$-kolorowalne ściany wtedy i tylko wtedy, gdy graf $\mathbf {M}$ jest eulerowski.

Dowód

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

Niech teraz $\mathbf {M}$ będzie grafem eulerowskim. Wtedy, na mocy wniosku z Twierdzenia Eulera, jego krawędzie można podzielić na rozłączne krawędziowo cykle $C_{1},\ldots ,C_{k}$. Kolorowanie ścian mapy $\mathbf {M}$ zdefiniujmy poprzez przypisanie ścianie pierwszego koloru, jeśli jest otoczona nieparzystą liczbą cykli spośród $C_{1},\ldots ,C_{k}$, 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 $C_{i}$, to jedna z tych ścian leży wewnątrz cyklu $C_{i}$, a druga na zewnątrz $C_{i}$. W stosunku do pozostałych cykli spośród $C_{1},\ldots ,C_{k}$, 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.

Z Twierdzenia Uzupelnic th 4barw planar|, poprzez przejście od mapy $\mathbf {M}$ do grafu geometrycznie dualnego $\mathbf {M} ^{*}$ dostajemy natychmiast następujący wniosek.

Wniosek 15

Każda mapa ma $4$-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 $\mathbf {G} =\left(\left\lbrace v_{1},\ldots ,v_{n}\right\rbrace ,E\right)$ będzie grafem prostym. Przy każdej permutacji $\rho :\left\lbrace 1,\ldots ,n\right\rbrace \longrightarrow \left\lbrace 1,\ldots ,n\right\rbrace$ każdemu wierzchołkowi $v_{\rho \left(i\right)}$ przypisana jest liczba sąsiadów $n_{\rho \left(i\right)}^{\rho }$ w zbiorze wierzchołków o indeksie mniejszym niż $\rho \left(i\right)$. Liczba stopniowa jest równa

$\chi _{s}\!\left(\mathbf {G} \right)=\min _{\rho }\max _{i=1,\ldots ,n}{n_{i}^{\rho }}.$

Przykład

Rozważmy graf $\mathbf {G} _{1}=\left(\left\lbrace v_{1},v_{2},v_{3},v_{4},v_{5}\right\rbrace ,E\right)$ przedstawiony na rysunku Uzupelnic grafy liczba stopniowa 1|.

{grafy_liczba_stopniowa_1} {Graf $\mathbf {G} _{1}$. [Rysunek z pliku: grafyliczbastopniowa1.eps]}

Dla permutacji $\rho$ zadanej przez

${\begin{array}{|c||c|c|c|c|c|}\hline n&1&2&3&4&5\\\hline \rho \left(n\right)&5&2&3&1&4\\\hline \end{array}}$

mamy $\max _{i=1,\ldots ,n}{n_{i}^{\rho }}=2$ i wartość ta jest realizowana przez wierzchołki $v_{3}$ i $v_{1}$. Wierzchołki ułożone w porządku $v_{\rho \left(1\right)},\ldots ,v_{\rho \left(5\right)}$ przedstawione są na rysunku Uzupelnic grafy liczba stopniowa 2|.

Przeglądając z kolei wszystkie możliwe permutacje możemy stwierdzić, że nasza permutacja $\rho$ realizuje minimum $\displaystyle {\min _{\rho }\max _{i=1,\ldots ,n}{n_{i}^{\rho }}}$, a zatem $\chi _{s}\!\left(\mathbf {G} \right)=2$.

{grafy_liczba_stopniowa_2} {Graf $\mathbf {G} _{1}$ z wierzhołkami w porządku wyznaczonym przez $\rho$. [Rysunek z pliku: grafyliczbastopniowa2.eps]}

Graf $\mathbf {G} _{1}$ można teraz pokolorować następującą procedurą. Wybierając kolejno wierzchołki $v_{\rho \left(1\right)},v_{\rho \left(2\right)},\ldots ,v_{\rho \left(5\right)}$ 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 $\mathbf {G} _{1}$. [Rysunek z pliku: grafyliczbastopniowa3.eps]}

Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.

Obserwacja 16

Jeżeli $\mathbf {G}$ jest grafem prostym, to

$\chi \!\left(\mathbf {G} \right)\leq \chi _{s}\!\left(\mathbf {G} \right)+1.$

Dowód

Niech $v_{1},\ldots ,v_{n}$ będzie ciągiem wierzchołków grafu $\mathbf {G}$ w porządku realizującym wartość $\chi _{s}\!\left(\mathbf {G} \right)$. Wskażemy kolorowanie za pomocą $\chi _{s}\!\left(\mathbf {G} \right)+1$ barw. Wierzchołki kolorowane są kolejno zgodnie z ich numeracją. Załóżmy, że pokolorowane zostały już wierzchołki $v_{1},\ldots ,v_{i-1}$. Wierzchołek $v_{i}$ ma co najwyżej $\chi _{s}\!\left(\mathbf {G} \right)$ sąsiadów w zbiorze $\left\lbrace v_{1},\ldots ,v_{i-1}\right\rbrace$, tak więc w zbiorze $\chi _{s}\!\left(\mathbf {G} \right)+1$ kolorów jest jeszcze co najmniej jeden kolor nie wykorzystany dla tych wcześniejszych sąsiadów $v_{i}$. Przydzielamy go więc wierzchołkowi $v_{i}$. 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)} .