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}) \).