6. Teoria grafów#
6.1. Podstawowe pojęcia#
Narration
Teoria grafów zajmuje się badaniem struktur złożonych z obiektów (wierzchołków) oraz relacji (krawędzi) łączących pary tych obiektów. Modelami grafowymi opisujemy między innymi:
relacje znajomości w grupie osób
plany labiryntów
sieci dróg
schematy obwodów elektrycznych
stan rozgrywek w turniejach sportowych
reprezentacje hierarchii danych.
Definicja 6.1
Grafem nieskierowanym (niezorientowanym) nazywamy parę
gdzie \(V = V(G) = \Set{v_1, \ldots, v_n}\) jest niepustym, skończonym zbiorem wierzchołków , natomiast \(E = E(G)\) jest skończoną rodziną nieuporządkowanych par (dwuelementowych podzbiorów) wierzchołków, zwanych krawędziami .
Uwaga 6.1
Krawędź łączącą wierzchołki \(u,v \in V\) zapisujemy krótko jako \(uv .\)
W sensie powyższej definicji nie dopuszczamy krawędzi postaci \(vv\) (łączącej wierzchołek sam ze sobą) nazywanej pętlą).
Nie dopuszczamy również kilku krawędzi łączących dwa wierzchołki (tak zwane krawędzie wielokrotne).
Ponieważ w wielu zastosowaniach zarówno pętle jak i krawędzie wielokrotne są przydatne, to rozważa się modyfikacje powyższej definicji (na przykład multigrafy dopuszczają krawędzie wielokrotne).
W niektórych źródłach powyższa definicja (bez pętli i bez krawędzi wielokrotnych) odnosi się do nieskierowanych grafów prostych, zaś samo pojęcie grafu dopuszcza te dwie możliwości.
Definicja 6.2
Wierzchołki \(u,v \in V\) połączone krawędzią \(uv \in E\) nazywamy sąsiednimi, a krawędź \(uv\) – incydentną z wierzchołkami \(u\) i \(v .\)
Stopniem wierzchołka \(v\), oznaczanym \(\deg(v)\), nazywamy liczbę krawędzi incydentnych z \(v\) (jeśli dopuszczamy pętle, to każdą liczymy dwukrotnie).
Uwaga 6.2
Wierzchołek stopnia \(0\) nazywamy izolowanym .
Wierzchołek stopnia \(1\) nazywamy liściem .
W grafie prostym stopień wierzchołka jest równy liczbie jego sąsiadów.
Lemat 6.1 (O uściskach dłoni)
Dla dowolnego grafu \(G=(V,E)\) zachodzi
W szczególności liczba wierzchołków o nieparzystym stopniu jest parzysta.
Przykład 6.1
Dla grafu \(G\) o wierzchołkach \(V=\Set{a,b,c,d}\) i krawędziach \(E=\Set{ab,bc,cd,da,ac}\) mamy
Suma stopni wynosi \(10 = 2\cdot 5\), co zgadza się z liczbą krawędzi \(|E|=5 .\)
6.2. Drogi, cykle i spójność#
Definicja 6.3
Drogą w grafie \(G\) nazywamy naprzemienny ciąg wierzchołków i krawędzi
taki, że każda krawędź \(e_i\) łączy wierzchołki \(v_{i-1}\) i \(v_i\), oraz żadna krawędź się nie powtarza. Liczbę \(k\) nazywamy długością drogi.
Drogę, w której dodatkowo wszystkie wierzchołki są różne, nazywamy drogą prostą.
Jeśli \(v_0=v_k\), drogę nazywamy zamkniętą lub cyklem.
Jeśli dodatkowo wierzchołki \(v_0,\ldots,v_{k-1}\) są parami różne, mówimy o cyklu prostym.
Graf niezawierający żadnego cyklu nazywamy acyklicznym.
Definicja 6.4
Graf \(G\) nazywamy spójnym, jeśli dla dowolnych dwóch wierzchołków \(u,v \in V(G)\) istnieje droga łącząca \(u\) i \(v .\)
Podgrafem grafu \(G=(V,E)\) nazywamy każdy graf \(H=(V_H,E_H)\) taki, że \(V_H \subseteq V\) oraz \(E_H \subseteq E .\)
Jeżeli graf \(G\) nie jest spójny, to każdy jego maksymalny spójny podgraf nazywamy składową grafu \(G .\)
Przykład 6.2
Rozważmy graf \(G=(V,E)\) z wierzchołkami \(V=\Set{a,b,c,d,e,f,g}\) i krawędziami \(E=\Set{ab,bc,cd,da,ac,df,fg}\).
Ciąg \((g,f,d,a,b,c,a)\) jest drogą (używa sześciu różnych krawędzi: \(gf,fd,da,ab,bc,ca\)), ale nie jest prosta – wierzchołek \(a\) powtarza się.
Natomiast ciąg \((a,b,c,a)\) to cykl prosty długości \(3 .\) Sama odnoga, czyli ciąg \((d,f,g)\), jest drogą prostą i – w oderwaniu od reszty grafu – acykliczna.
Ponieważ wierzchołek \(e\) nie ma żadnych krawędzi, cały graf \(G\) nie jest spójny – ma dwie składowe: \(\Set{a,b,c,d,f,g}\) oraz \(\Set{e}\).
Trójkąt \(H=(\Set{a,b,c},\Set{ab,bc,ac})\) jest podgrafem pierwszej składowej.
Przykład 6.3
Rozważmy graf \(G=(V,E)\) złożony z 9 wierzchołków oraz dwóch podzbiorów krawędzi \(E_1=\Set{ab,ac,bd,be,cf,cg}\) oraz \(E_2=\Set{hi,ij,jh}\).
Ciąg \((d,b,a,c,g)\) jest drogą prostą długości \(4\) w części drzewiastej grafu; ponieważ cała ta część nie zawiera żadnego cyklu, jest acykliczna.
Kontrastowo, ciąg \((h,i,j,h)\) jest cyklem prostym długości \(3\) w drugiej części grafu.
Graf \(G\) nie jest spójny – ma dwie składowe: drzewo \(\Set{a,b,c,d,e,f,g}\) oraz trójkąt \(\Set{h,i,j}\).
Biorąc \(H=(\Set{a,b,c},\Set{ab})\) (a więc pomijając krawędź \(ac\)), widzimy, że podgraf nie musi zawierać wszystkich krawędzi łączących swoje wierzchołki.
6.3. Podstawowe klasy grafów#
Narration
Wśród wszystkich grafów wyróżnia się kilka klas o szczególnie regularnej strukturze, które posłużą nam jako podstawowe przykłady i „cegiełki” w dalszej części wykładu.
Definicja 6.5
Grafem pustym (bezkrawędziowym) nazywamy graf \(N_n=(V,E)\) o \(|V|=n\) wierzchołkach, w którym \(E=\emptyset .\) Każdy wierzchołek grafu pustego jest izolowany, tzn. \(\deg(v)=0\) dla każdego \(v\in V .\)
Definicja 6.6
Grafem pełnym nazywamy graf \(K_n=(V,E)\) o \(n\) wierzchołkach, w którym każde dwa różne wierzchołki są sąsiednie, czyli
Liczba krawędzi grafu pełnego wynosi \(|E|=\binom n 2 .\)
Definicja 6.7
Dla ustalonego \(k\in\nn_0\), graf \(G=(V,E)\) nazywamy \(k\)-regularnym, jeśli \(\deg(v)=k\) dla każdego \(v\in V .\)
Graf nazywamy regularnym, jeśli jest \(k\)-regularny dla pewnego \(k .\)
Definicja 6.8
Dla \(n\geq 3\), cyklem \(C_n\) nazywamy spójny i \(2\)-regularny graf o \(n\) wierzchołkach.
Definicja 6.9
Dla \(n\geq 2\), grafem liniowym (ścieżką) \(P_n\) nazywamy graf powstały przez usunięcie dowolnej krawędzi z cyklu \(C_n .\)
Definicja 6.10
Graf \(G\) nazywamy drzewem , jeśli jest spójny i acykliczny.
Wierzchołki stopnia \(1\) w drzewie nazywamy liśćmi , a pozostałe – wierzchołkami wewnętrznymi .
Definicja 6.11
Graf \(G\) nazywamy lasem , jeśli jest acykliczny (niekoniecznie spójny).
Uwaga 6.3
Grafy puste i pełne to skrajne przypadki grafów regularnych – odpowiednio \(0\)-regularne i \((n-1)\)-regularne na \(n\) wierzchołkach.
W odróżnieniu od cyklu, graf \(P_n\) nie jest regularny (dwa końcowe wierzchołki mają stopień \(1\), pozostałe – stopień \(2\)).
Drzewo o \(n\) wierzchołkach ma dokładnie \(n-1\) krawędzi.
Jest to zresztą równoważna charakteryzacja drzewa (graf jest spójny o \(n-1\) krawędziach wtedy i tylko wtedy, gdy jest drzewem).
Las to rozłączna suma drzew – jego składowe (w sensie wcześniejszej definicji) są drzewami.
W szczególności graf pusty \(N_n\) jest lasem złożonym z \(n\) jedno-wierzchołkowych drzew.
Ścieżka \(P_n\) i każde drzewo są grafami acyklicznymi, ale nie każdy graf acykliczny jest spójny – stąd potrzebne jest osobne pojęcie lasu.
6.4. Grafy dwudzielne#
Definicja 6.12
Graf \(G=(V,E)\) nazywamy dwudzielnym, jeśli zbiór \(V\) można podzielić na dwa rozłączne podzbiory \(V_1, V_2\) (klasy podziału) tak, że żadne dwa wierzchołki należące do tej samej klasy nie są sąsiednie.
Piszemy wtedy \(G(V_1,V_2) .\)
Przykład 6.4
Cykl \(C_6\) jest dwudzielny – wierzchołki można podzielić na dwie klasy \(V_1 = \Set{1,3,5}\) i \(V_2 = \Set{2,4,6}\) , odwiedzane na przemian.
Niech \(Q_3=(V,E)\) będzie grafem sześcianu: wierzchołkami są wszystkie ciągi binarne długości \(3\) (czyli \(V=\Set{0,1}^3\), \(|V|=8\)), a krawędź łączy dwa ciągi wtedy i tylko wtedy, gdy różnią się dokładnie na jednej pozycji.
\(Q_3\) jest grafem dwudzielnym \(G(V_1,V_2)\), gdzie
\(V_1 = \Set{\text{ciągi o parzystej liczbie jedynek}}\)
\(V_2 = \Set{\text{ciągi o nieparzystej liczbie jedynek}} .\)
Istotnie, zmiana jednej współrzędnej zawsze zmienia parzystość liczby jedynek o dokładnie jeden, więc żadna krawędź nie łączy dwóch wierzchołków z tej samej klasy.
Patrząc wyłącznie na strukturę grafu (bez etykiet i kolorów) dwudzielność \(Q_3\) wcale nie rzuca się w oczy – ujawnia się dopiero po pokolorowaniu wierzchołków zgodnie z parzystością.
\(Q_3\) jest grafem \(3\)-regularnym – widać więc, że regularność i dwudzielność to własności od siebie niezależne.
Definicja 6.13
Graf dwudzielny \(G(V_1,V_2)\), w którym każdy wierzchołek z \(V_1\) jest połączony z każdym wierzchołkiem z \(V_2\), nazywamy pełnym grafem dwudzielnym i oznaczamy przez \(K_{r,s}\), gdzie \(r=|V_1|\), \(s=|V_2| .\)
Graf \(K_{1,s}\) nazywamy gwiazdą .
Uwaga 6.4
W grafie \(K_{r,s}\) liczba wierzchołków wynosi \(r+s\), a liczba krawędzi \(r\cdot s .\)
Twierdzenie 6.2
Graf \(G\) jest dwudzielny wtedy i tylko wtedy, gdy każdy jego cykl ma parzystą długość.
W szczególności każdy graf acykliczny jest dwudzielny.
Przykład 6.5
Cykl \(C_5\) ma długość \(5\) (nieparzystą), więc \(C_5\) nie jest dwudzielny.
Rozważmy graf \(G\) powstały z cyklu \(C_6\) z dodaną jedną krawędzią.
Sam cykl \(C_6\) jest dwudzielny, jednak dodana przekątna łączy dwa wierzchołki „tego samego koloru” – \(G\) przestaje być dwudzielny.
Najłatwiej to udowodnić wskazując nieparzysty cykl.
Ten przykład pokazuje, że obecność dużego, parzystego cyklu jako „szkieletu” grafu nie wystarcza, by wnioskować o jego dwudzielności.
Trzeba sprawdzić wszystkie cykle w grafie, a nie tylko ten najbardziej oczywisty.
6.5. Problem mostów królewieckich#
Narration
W 1736 roku Leonhard Euler rozwiązał następujący problem. Przez miasto Królewiec (dzisiejszy Kaliningrad) przepływa rzeka Pregoła, dzieląc miasto na cztery części, połączone siedmioma mostami. Mieszkańcy zastanawiali się, czy można odbyć spacer po mieście, przechodząc przez każdy most dokładnie raz i wracając do punktu wyjścia.
Uwaga 6.5
Sytuację tę można przedstawić jako multigraf \(G=(V,E)\), w którym wierzchołki \(V=\Set{A,B,C,D}\) odpowiadają czterem częściom miasta, a siedem krawędzi – siedmiu mostom (niektóre pary części miasta są połączone więcej niż jednym mostem).
Definicja 6.14
Drogą Eulera w grafie \(G\) nazywamy drogę zawierającą każdą krawędź grafu \(G\) dokładnie raz (wierzchołki mogą się powtarzać).
Zamkniętą drogę Eulera nazywamy cyklem Eulera.
Graf, w którym istnieje cykl Eulera, nazywamy grafem eulerowskim.
Twierdzenie 6.3 (Kryterium Eulera)
W (multi)grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek ma parzysty stopień.
Przykład 6.6
W grafie mostów królewieckich mamy \(\deg(A)=5\), \(\deg(B)=\deg(C)=\deg(D)=3\) – wszystkie cztery wierzchołki mają stopień nieparzysty. Na mocy powyższego twierdzenia nie istnieje więc ani cykl, ani nawet droga Eulera: nie da się przejść przez wszystkie mosty, korzystając z każdego dokładnie raz.
Uwaga 6.6
Spójne grafy \(n\)-regularne są eulerowskie wtedy i tylko wtedy, gdy \(n\) jest parzyste.
Stąd na przykład \(K_{5}\) i \(C_6\) są eulerowskie (są odpowiednio \(2\)- i \(4\)-regularne), zaś \(K_6\) nie jest eulerowski.
Kryterium Eulera ma poglądowe zastosowanie do popularnej zagadki:
Narysuj dany rysunek jednym pociągnięciem, nie odrywając ołówka od kartki i nie kreśląc żadnej linii dwukrotnie.
Pytanie to jest dokładnie pytaniem o istnienie drogi (lub cyklu) Eulera w grafie odpowiadającym temu rysunkowi.
Rysunek da się nakreślić jednym pociągnięciem wtedy i tylko wtedy, gdy ma on zero lub dwa wierzchołki nieparzystego stopnia (jeśli dwa, to trzeba zacząć w jednym z nich i skończyć w drugim).
Gdy graf nie jest eulerowski (ma więcej niż dwa wierzchołki nieparzystego stopnia), naturalne staje się pytanie:
O ile najmniej trzeba „wydłużyć” trasę (dopuszczając ponowne przejście po już odwiedzonych krawędziach), aby przejść każdą krawędź co najmniej raz i wrócić do punktu startu?
To tak zwany problem chińskiego listonosza – odpowiada on np. listonoszowi, który musi dostarczyć przesyłki na każdą ulicę swojego rejonu i wrócić na pocztę, pokonując możliwie najkrótszą trasę.
Rozwiązanie polega na sparowaniu wszystkich wierzchołków nieparzystego stopnia (jest ich parzyście wiele, na mocy lematu o uściskach dłoni) i podwojeniu krawędzi na najkrótszych drogach łączących każdą parę.
W odróżnieniu od pokrewnego, ale znacznie trudniejszego problemu komiwojażera (związanego z cyklem Hamiltona), problem chińskiego listonosza daje się rozwiązać efektywnie, w czasie wielomianowym.
6.6. Grafy Hamiltona#
Definicja 6.15
Cyklem Hamiltona nazywamy cykl prosty zawierający wszystkie wierzchołki grafu \(G .\)
Graf, w którym istnieje cykl Hamiltona, nazywamy grafem hamiltonowskim.
Uwaga 6.7
W odróżnieniu od grafów Eulera (gdzie kluczowa jest liczba krawędzi), warunek hamiltonowskości dotyczy wszystkich wierzchołków.
Nie znamy prostej charakteryzacji analogicznej do twierdzenia Eulera – sprawdzenie hamiltonowskości grafu jest w ogólności trudne obliczeniowo.
Twierdzenie 6.4 (Diraca)
Niech \(G\) będzie grafem prostym o \(n\geq 3\) wierzchołkach. Jeżeli
to \(G\) jest hamiltonowski.
Przykład 6.7
Graf pełny \(K_n\) dla \(n\geq 3\) jest hamiltonowski – spełnia (z nadmiarem) założenie twierdzenia Diraca, gdyż \(\deg(v) = n-1 \geq \frac n 2 .\)
Przykład 6.8 (Droga Hamiltona w grafie ruchów skoczka)
Skoczek szachowy porusza się o wektor \((\pm 1, \pm 2)\) lub \((\pm 2, \pm 1)\). Na planszy \(4\times 5\) (20 pól) istnieje otwarta trasa skoczka – czyli droga Hamiltona w grafie, którego wierzchołkami są pola planszy, a krawędziami legalne ruchy skoczka.
Skoczek zawsze przemieszcza się z pola jednego koloru na pole koloru przeciwnego – to dwukolorowanie pokazuje, że graf ruchów skoczka jest dwudzielny.
Ćwiczenie 6.1
Czy graf pełny dwudzielny \(K_{2,3}\) jest hamiltonowski.
Rozwiązanie
Cykl Hamiltona w grafie dwudzielnym \(G(V_1,V_2)\) musi na przemian odwiedzać wierzchołki z \(V_1\) i z \(V_2\), co wymaga \(|V_1|=|V_2| .\)
Dla \(K_{2,3}\) mamy \(|V_1|=2 \neq 3=|V_2|\), więc graf ten nie jest hamiltonowski.
6.7. Grafy planarne i wzór Eulera#
Narration
Każdy graf można narysować na płaszczyźnie, przyporządkowując wierzchołkom punkty, a krawędziom – łuki krzywych łączące odpowiednie punkty. Interesujące jest jednak, czy da się to zrobić bez przecięć krawędzi.
Definicja 6.16
Graf nazywamy planarnym, jeśli można jego reprezentację narysować na płaszczyźnie tak, aby żadne dwie krawędzie się nie przecinały (poza wspólnymi końcami).
Konkretny taki rysunek nazywamy grafem płaskim.
Przykład 6.9
Grafami planarnymi są między innymi: graf pusty, graf pełny \(K_4\), wszystkie cykle \(C_n\), wszystkie gwiazdy \(K_{1,s}\), a także każdy podgraf grafu planarnego.
Uwaga 6.8
W sensie przyjętej definicji grafu, pojęcie grafu płaskiego jest sztuczne – graf to przecież para zbiorów nie mających nic wspólnego z płaszczyzną.
Graf płaski dzieli płaszczyznę na obszary zwane ścianami. Jedna z nich, nieograniczona, to ściana zewnętrzna.
Twierdzenie 6.5 (Wzór Eulera)
Dla dowolnego spójnego grafu płaskiego \(G=(V,E)\) o:
\(W=|V|\) wierzchołkach,
\(K=|E|\) krawędziach i
\(S\) ścianach
zachodzi zależność
Wniosek 6.6
Z wzoru Eulera wynika, że
dla każdego prostego grafu planarny o \(W\geq 3\) wierzchołkach spełniona jest nierówność
jeśli dodatkowo jest dwudzielny, to wówczas
Przykład 6.10
Graf pełny dwudzielny \(K_{3,3}\) ma \(W=6\) wierzchołków oraz \(K=3\cdot 3=9\) krawędzi.
Pierwsza z powyższych nierówności jest spełniona:
więc sama w sobie nie wystarcza, by wykluczyć planarność \(K_{3,3} .\)
Jednak \(K_{3,3}\) jest grafem dwudzielnym, więc gdyby był planarny, musiałby spełniać ostrzejszą nierówność \(K\leq 2W-4 .\) Tymczasem
Zatem \(K_{3,3}\) nie jest planarny.
Ćwiczenie 6.2
Korzystając ze wzoru Eulera, pokażmy, że graf \(K_5\) nie jest planarny.
Rozwiązanie
Graf \(K_5\) ma \(W=5\) wierzchołków oraz \(K=\binom 5 2 = 10\) krawędzi. Gdyby \(K_5\) był planarny, to z nierówności \(K\leq 3W-6\) mielibyśmy
co jest fałszem. Zatem \(K_5\) nie jest planarny.
Definicja 6.17
Grafami Kuratowskiego nazywamy grafy \(K_5\) oraz \(K_{3,3} .\)
Twierdzenie 6.7 (Kuratowski)
Graf \(G\) jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu będącego podziałem grafu Kuratowskiego.
Uwaga 6.9
Każdy graf zawierający \(K_5\) lub \(K_{3,3}\) jako podgraf jest nieplanarny.
Jednak warunek w twierdzeniu Kuratowskiego musi być nieco słabszy – dotyczyć dowolnych podziałów tych grafów, bo istnieją grafy nieplanarne, które nie zawierają podgrafu Kuratowskiego.
Klasycznym przykładem jest graf Petersena, którego model widać na rysunku.
Po usunięciu wierzchołka \(5\) (wraz z jego trzema krawędziami) wierzchołki w \(V_1 = \Set{0,2,6}\) i \(V_2 = \Set{1,3,9}\) odpowiadają dwóm trójkom wierzchołków rozgałęzienia \(K_{3,3}\), a wierzchołki \(4,7,8\) są punktami podziału na krawędziach \(0\!-\!4\!-\!3\), \(2\!-\!7\!-\!9\) oraz \(6\!-\!8\!-\!1 .\)
Ponieważ podział grafu nieplanarnego jest sam w sobie nieplanarny (podział „wydłuża” krawędzie, ale nie zmienia struktury przecięć), z twierdzenia Kuratowskiego wynika, że cały graf Petersena – jako zawierający podział \(K_{3,3}\) – jest nieplanarny.
6.8. Kolorowanie grafów#
Definicja 6.18
Graf \(G\) nazywamy \(k\)-kolorowalnym wierzchołkowo, jeśli jego wierzchołki można pokolorować co najwyżej \(k\) kolorami tak, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru.
Liczbą chromatyczną grafu \(G\), oznaczaną \(\chi(G)\), nazywamy najmniejszą liczbę \(k\), dla której \(G\) jest \(k\)-kolorowalny.
Uwaga 6.10
Graf jest \(2\)-kolorowalny wtedy i tylko wtedy, gdy jest dwudzielny – stąd \(\chi(K_{r,s})=2 .\)
Dla cyklu \(C_n\): \(\ \chi(C_n)=2\), gdy \(n\) jest parzyste, oraz \(\chi(C_n)=3\), gdy \(n\) jest nieparzyste.
Dla grafu pełnego \(\chi(K_n) = n .\)
Przykład 6.11
Graf Petersena zawiera cykle nieparzystej długości (np. pięciokąt zewnętrzny), więc nie jest dwudzielny, czyli \(\chi(G) \geq 3 .\)
Kolorowanie trzema kolorami widać na rysunku, więc
\[ \chi(\text{graf Petersena}) = 3. \]Graf koła \(W_5\): cykl \(C_5\) na wierzchołkach \(1,\ldots,5\), do którego dodajemy wierzchołek centralny \(0\) połączony krawędzią z każdym wierzchołkiem \(C_5.\)
\(W_5\) jest oczywiście planarny.
Jednocześnie \(\chi(W_5)=4\):
Ponieważ \(1,\ldots,5\) tworzą cykl nieparzystej długości, potrzeba do jego pokolorowania co najmniej \(3\) kolorów, więc \(\chi(W_5)\geq 3 .\)
Co więcej, hub \(0\) jest połączony z każdym wierzchołkiem obwodu, więc jego kolor musi różnić się od wszystkich kolorów użytych na obwodzie – na \(0\) trzeba użyć czwartego koloru. Stąd \(\chi(W_5)\geq 4 .\)
Z drugiej strony, \(4\)-kolorwanie jest łatwe do uzyskania.
Narration
Motywacją historyczną teorii kolorowania grafów był problem czterech barw:
Czy każdą mapę polityczną na płaszczyźnie można pokolorować tak, aby kraje sąsiednie (o wspólnej granicy) miały różne barwy, używając co najwyżej czterech kolorów?
Mapę taką przedstawiamy jako graf planarny (kraje – wierzchołki, wspólna granica – krawędź), a pytanie sprowadza się do zbadania jego liczby chromatycznej.
Twierdzenie 6.8 (o czterech barwach)
Każdy graf planarny jest \(4\)-kolorowalny.
Uwaga 6.11
Twierdzenie to ma burzliwą historię: postawione zostało w 1852 roku (F. Guthrie), błędny dowód opublikował A. Kempe w 1879 roku, a błąd w nim wykryto dopiero w 1890 roku (P. Heawood). Poprawny dowód Appla i Hakena z 1976 roku był pierwszym istotnie wykorzystującym wspomaganie komputerowe (analizę tysięcy przypadków), co budziło (i wciąż budzi) dyskusje na temat statusu takiego dowodu w matematyce.
Dowód słabszego twierdzenia o \(6\)-kolorowalności grafów planarnych opiera się na indukcji względem liczby wierzchołków oraz na fakcie, że każdy graf planarny ma wierzchołek stopnia co najwyżej \(5\) (co wynika ze wzoru Eulera).
6.9. Skojarzenia i twierdzenie Halla#
Narration
Rozważmy grupę \(n\) dziewcząt i grupę \(n\) chłopców, gdzie każda dziewczyna zna pewien podzbiór chłopców. Problem małżeństw opera się na pytaniu:
Czy każdą z dziewcząt można wydać za mąż za jednego ze znanych jej chłopców
(tak, aby żaden chłopiec nie poślubił dwóch dziewcząt)?
Sytuację modelujemy grafem dwudzielnym \(G(V_1,V_2)\), gdzie \(V_1\) to zbiór dziewcząt, \(V_2\) – chłopców, a krawędź łączy dziewczynę z chłopcem, jeśli się znają.
Definicja 6.19
Skojarzeniem w grafie \(G=(V,E)\) nazywamy dowolny zbiór krawędzi \(M \subseteq E\), z których żadne dwie nie mają wspólnego wierzchołka.
Dla \(X\subseteq V\), skojarzenie \(M\) nazywamy \(X\)-nasycającym, jeśli każdy wierzchołek zbioru \(X\) należy do pewnej krawędzi z \(M .\)
Skojarzenie \(M\) nazywamy pełnym, jeśli jest \(V\)-nasycające.
Uwaga 6.12
Rozwiązanie problemu małżeństw istnieje wtedy i tylko wtedy, gdy w grafie \(G(V_1,V_2)\) istnieje skojarzenie \(V_1\)-nasycające.
Warunkiem koniecznym istnienia takiego skojarzenia jest, aby każda grupa \(k\) dziewcząt znała łącznie co najmniej \(k\) chłopców – w przeciwnym razie nie dałoby się ich wszystkich skojarzyć z różnymi chłopcami.
Okazuje się, że jest to warunek dostateczny, o czym mówi twierdzenie Halla.
Twierdzenie 6.9 (Halla o małżeństwach)
Niech \(G(V_1,V_2)\) będzie grafem dwudzielnym.
Dla \(A\subseteq V_1\) oznaczmy przez \(N(A)\subseteq V_2\) zbiór wszystkich sąsiadów wierzchołków z \(A .\)
Wówczas w grafie \(G(V_1,V_2)\) istnieje skojarzenie \(V_1\)-nasycające wtedy i tylko wtedy, gdy
(tzw. warunek Halla).
Wniosek 6.10
W każdym dwudzielnym grafie regularnym istnieje pełne skojarzenie.
Przykład 6.12
Różne liczności klas.
Rozważmy graf \(G(V_1,V_2)\) z \(V_1=\Set{a,e}\), \(V_2=\Set{b,d,h,k}\) i krawędziami \(E=\Set{ad,ah,ak,ed,eh} .\)
Mamy \(|V_1|=2<4=|V_2| .\)
Warunek Halla jest spełniony dla każdego \(A\subseteq V_1 .\)
Istnieje skojarzenie \(V_1\)-nasycające.
Twierdzenie Halla nie wymaga równości \(|V_1|=|V_2| .\)
Wąskie gardło trudne do wykrycia.
Rozważmy graf \(G(V_1,V_2)\) z \(V_1=\Set{a,e,i,o}\), \(V_2=\Set{b,d,h,k}\) i krawędziami \(E=\Set{ab,ad,eb,ed,ib,id,ob,od,oh,ok} .\)
Pojedyncze wierzchołki i pary z \(V_1\) spełniają warunek Halla.
Dla \(A=\Set{a,e,i}\) mamy \(|N(A)|=2<3=|A| .\)
Warunek Halla zawodzi. Skojarzenie \(V_1\)-nasycające nie istnieje.
Graf dwudzielny regularny.
Rozważmy graf \(G(V_1,V_2)\) z \(V_1=\Set{a,e,i}\), \(V_2=\Set{b,d,h}\) i krawędziami \(E=\Set{ab,be,ed,di,ih,ha} .\)
Każdy wierzchołek ma stopień \(2 .\) Graf jest \(2\)-regularny i dwudzielny.
Na mocy wcześniejszego wniosku istnieje skojarzenie pełne.
Pełny graf dwudzielny bez jednego skojarzenia doskonałego.
Skojarzeniem doskonałym nazywamy skojarzenie pełne w grafie z \(|V_1|=|V_2|\) – takie, które jednocześnie nasyca \(V_1\) i \(V_2 .\)
Nieporządkiem \(n\)-elementowym nazywamy permutację \(\pi\) zbioru \(\Set{1,\ldots,n}\) bez punktów stałych, tzn. \(\pi(k)\neq k\) dla każdego \(k .\) Liczbę nieporządków oznaczamy \(D_n .\)
Rozważmy graf \(G(V_1,V_2)\) z \(V_1=\Set{a,e,i,o}\), \(V_2=\Set{b,d,h,k} .\) Startujemy od pełnego grafu dwudzielnego \(K_{4,4}\) i usuwamy skojarzenie doskonałe \(\Set{ab,ed,ih,ok} .\)
Warunek Halla pozostaje spełniony.
Skojarzenia doskonałe w grafie \(G\) odpowiadają bijekcjom \(V_1\to V_2\) omijającym usunięte krawędzie – czyli nieporządkom.
Jest ich dokładnie \(D_4=9 .\)
