Informatyka MIMUW

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}=( V,E )$ 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\!( \mathbf{G} )$, 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\!( \mathbf{G} )$ kolorów.

Twierdzenie 14.9

Graf, którego wszystkie wierzchołki mają stopień nie większy niż $k$ jest $(k+1)$-kolorowalny.

Dowód

Dowód poprowadzimy indukcyjnie ze względu na liczbę wierzchołków w grafie $\mathbf{G}=( V,E )$. Jeśli graf ma jeden wierzchołek, to oczywiście wystarcza jeden kolor. Załóżmy więc, że $\vert V \vert\geq2$. Wybierzmy dowolny wierzchołek $v\in V$ i rozważmy graf $\mathbf{G}|_{V-\lbrace v \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-\lbrace x \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 14.9 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 14.9, ale podajemy je bez dowodu.

Twierdzenie 14.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 14.11

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

Dowód

Zauważmy najpierw, że w grafie dwudzielnym $\mathbf{G}=( V_1\cup V_2,E )$, 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 14.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}=( V,E )$. Dla $\vert V \vert=1$ teza jest oczywista. Niech więc $\vert V \vert\geq2$. Z Wniosku 14.6 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-\lbrace v \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 Grafy 5barw planar.

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

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 14.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.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 14.13, poprzez przejście od mapy $\mathbf{M}$ do grafu geometrycznie dualnego $\mathbf{M}^*$ dostajemy natychmiast następujący wniosek.

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

$\chi_s\!( \mathbf{G} )= \min_{\rho}\max_{i=1,\ldots, n}{n_i^{\rho}}.$

Przykład

Rozważmy graf $\mathbf{G}_1=( \lbrace v_1,v_2,v_3,v_4,v_5 \rbrace,E )$ przedstawiony na rysunku Grafy liczba stopniowa 1.

Dla permutacji $\rho$ zadanej przez

$\begin{array} {|c||c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 \\ \hline \rho( n ) & 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( 1 )},\ldots,v_{\rho( 5 )}$ przedstawione są na rysunku Graf G_1 z wierzchołkami....

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\!( \mathbf{G} )=2$.

Graf $\mathbf{G}_1$ można teraz pokolorować następującą procedurą. Wybierając kolejno wierzchołki $v_{\rho( 1 )},v_{\rho( 2 )},\ldots,v_{\rho( 5 )}$ nadajemy im kolor niewykorzystany dla żadnego dotąd rozpatrywanego sąsiada. Otrzymujemy wtedy kolorowanie przedstawione na rysunku Kolorowanie grafu.

Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.

Obserwacja 14.16

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

$\chi\!( \mathbf{G} )\leq\chi_s\!( \mathbf{G} )+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\!( \mathbf{G} )$. Wskażemy kolorowanie za pomocą $\chi_s\!( \mathbf{G} )+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\!( \mathbf{G} )$ sąsiadów w zbiorze $\lbrace v_1,\ldots,v_{i-1} \rbrace$, tak więc w zbiorze $\chi_s\!( \mathbf{G} )+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 ${\sf V}\!(\mathbf{G})$.