Matematyka dyskretna 1/Wykład 14: Grafy III: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 3: Linia 3:
 
'''Graf płaski''' to para:  
 
'''Graf płaski''' to para:  
 
<math>\mathbf{\overline{G}}=\left( \overline{V},\overline{E} \right)</math>, gdzie
 
<math>\mathbf{\overline{G}}=\left( \overline{V},\overline{E} \right)</math>, gdzie
 
 
* <math>\overline{V}</math> jest  jakimś zbiorem punktów płaszczyzny <math>\mathbb{R}^2</math>,
 
* <math>\overline{V}</math> jest  jakimś zbiorem punktów płaszczyzny <math>\mathbb{R}^2</math>,
 
 
* <math>\overline{E}</math> jest zbiorem nie przecinających się odcinków lub łuków w <math>R^2</math>  
 
* <math>\overline{E}</math> jest zbiorem nie przecinających się odcinków lub łuków w <math>R^2</math>  
 
o końcach ze zbiorze <math>\overline{V}</math>.
 
o końcach ze zbiorze <math>\overline{V}</math>.
  
 
'''Graf planarny''' to graf, który jest prezentowalny jako graf płaski.
 
'''Graf planarny''' to graf, który jest prezentowalny jako graf płaski.
 
[!h]
 
  
 
{grafy_planarne}
 
{grafy_planarne}
 
{Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c) '''[Rysunek z pliku:''' <tt>grafyplanarne.eps</tt>''']'''}
 
{Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c) '''[Rysunek z pliku:''' <tt>grafyplanarne.eps</tt>''']'''}
  
{{obserwacje|[Uzupelnij]||
+
{{obserwacje|1||
  
 
Grafy <math>\mathcal{K}_{5}</math> i <math>\mathcal{K}_{3,3}</math> nie są planarne.  
 
Grafy <math>\mathcal{K}_{5}</math> i <math>\mathcal{K}_{3,3}</math> nie są planarne.  
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Graf <math>\mathcal{K}_{3,3}</math> ma sześcio-elementowy cykl Hamiltona <math>H</math>.  
 
Graf <math>\mathcal{K}_{3,3}</math> ma sześcio-elementowy cykl Hamiltona <math>H</math>.  
 
Musi on być narysowany w dowolnej płaskiej prezentacji.
 
Musi on być narysowany w dowolnej płaskiej prezentacji.
 
Przykładowe umiejscowienie tego cyklu prezentuje rys. [[##pict k33|Uzupelnic pict k33|]].
 
Przykładowe umiejscowienie tego cyklu prezentuje rys. [[##pict k33|Uzupelnic pict k33|]].
 
[!h]
 
  
 
{grafy_k33}
 
{grafy_k33}
Linia 36: Linia 30:
 
W konsekwencji nie da się narysować krawędzi <math>v_3 v_0</math> nie przecinając krawędzi  
 
W konsekwencji nie da się narysować krawędzi <math>v_3 v_0</math> nie przecinając krawędzi  
 
<math>v_1 v_4</math> lub <math>v_2 v_5</math>.
 
<math>v_1 v_4</math> lub <math>v_2 v_5</math>.
 
[!h]
 
  
 
{grafy_k332}
 
{grafy_k332}
Linia 49: Linia 41:
 
że żaden graf zawierający <math>\mathcal{K}_{5}</math> lub <math>\mathcal{K}_{3,3}</math> nie jest planarny.
 
że żaden graf zawierający <math>\mathcal{K}_{5}</math> lub <math>\mathcal{K}_{3,3}</math> nie jest planarny.
 
Ale również graf powstały np. z <math>\mathcal{K}_{5}</math> poprzez umieszczenie na jednej krawędzi  
 
Ale również graf powstały np. z <math>\mathcal{K}_{5}</math> poprzez umieszczenie na jednej krawędzi  
dodatkowego wierzchołka nie jest planarny mimo,  
+
dodatkowego wierzchołka nie jest planarny mimo, że nie zawiera podgrafu <math>\mathcal{K}_{5}</math> ani <math>\mathcal{K}_{3,3}</math>.
że nie zawiera podgrafu <math>\mathcal{K}_{5}</math> ani <math>\mathcal{K}_{3,3}</math>.
+
Dla scharakteryzowania grafów planarnych potrzebne nam będzie następujące pojęcie homeomorficzności grafów.
Dla scharakteryzowania grafów planarnych  
 
potrzebne nam będzie następujące pojęcie homeomorficzności grafów.
 
  
 
Graf <math>\mathbf{G}_1</math> jest ''homeomorficzny'' z grafem <math>\mathbf{G}_2</math>,
 
Graf <math>\mathbf{G}_1</math> jest ''homeomorficzny'' z grafem <math>\mathbf{G}_2</math>,
 
jeśli jeden otrzymamy z drugiego poprzez wykonanie skończenie wielu poniższych operacji:  
 
jeśli jeden otrzymamy z drugiego poprzez wykonanie skończenie wielu poniższych operacji:  
 +
* Dodawanie wierzchołków stopnia dwa na krawędzi.<br> Jeśli <math>uw\in{\sf E}\!\left(\mathbf{G}_1\right)</math> oraz <math>x\not\in{\sf V}\!\left(\mathbf{G}_1\right)</math>, to operacja ta zastępuje graf <math>\left( {\sf V}\!\left(\mathbf{G}_1\right),{\sf E}\!\left(\mathbf{G}_1\right) \right)</math> grafem <math>\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)</math>.
 +
* Usuwanie wierzchołków stopnia dwa.<br>Jeśli <math>x\in{\sf V}\!\left(\mathbf{G}_1\right)</math> ma jedynie dwóch sąsiadów <math>u,w</math>, to operacja ta zastępuje graf <math>\left( {\sf V}\!\left(\mathbf{G}_1\right),{\sf E}\!\left(\mathbf{G}_1\right) \right)</math> grafem <math>\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)</math>.
  
* Dodawanie wierzchołków stopnia dwa na krawędzi.<br>
+
{{przyklad|||
Jeśli <math>uw\in{\sf E}\!\left(\mathbf{G}_1\right)</math> oraz <math>x\not\in{\sf V}\!\left(\mathbf{G}_1\right)</math>,
 
to operacja ta zastępuje graf <math>\left( {\sf V}\!\left(\mathbf{G}_1\right),{\sf E}\!\left(\mathbf{G}_1\right) \right)</math> grafem
 
<math>\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)</math>.
 
 
 
* Usuwanie wierzchołków stopnia dwa.<br>
 
Jeśli <math>x\in{\sf V}\!\left(\mathbf{G}_1\right)</math> ma jedynie dwóch sąsiadów <math>u,w</math>,
 
to operacja ta zastępuje graf <math>\left( {\sf V}\!\left(\mathbf{G}_1\right),{\sf E}\!\left(\mathbf{G}_1\right) \right)</math> grafem
 
<math>\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)</math>.
 
 
 
{{przyklad|[Uzupelnij]||
 
  
 
Grafy <math>\mathbf{G},\mathbf{G}'</math> przedstawione na rysunku [[##pict homeomorficzne|Uzupelnic pict homeomorficzne|]]  
 
Grafy <math>\mathbf{G},\mathbf{G}'</math> przedstawione na rysunku [[##pict homeomorficzne|Uzupelnic pict homeomorficzne|]]  
Linia 73: Linia 55:
 
zaś <math>\mathbf{G}''</math> nie jest homeomorficzny  
 
zaś <math>\mathbf{G}''</math> nie jest homeomorficzny  
 
ani z <math>\mathbf{G}</math> ani z <math>\mathbf{G}'</math>.  
 
ani z <math>\mathbf{G}</math> ani z <math>\mathbf{G}'</math>.  
 
[!h]
 
  
 
{grafy_homeomorficzne}
 
{grafy_homeomorficzne}
Linia 84: Linia 64:
 
Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.
 
Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|2 [Kuratowski 1930]||
[Kuratowski 1930]
 
  
 
Graf jest planarny wtedy i tylko wtedy,  
 
Graf jest planarny wtedy i tylko wtedy,  
Linia 94: Linia 73:
 
pojęcia sciągalności, lub grafu ilorazowego.
 
pojęcia sciągalności, lub grafu ilorazowego.
 
Przypomnijmy, że
 
Przypomnijmy, że
 
+
*  '''iloraz''' grafu <math>\mathbf{G}</math> przez relację równoważności <math>\theta\subseteq V\times V</math> na zbiorze jego wierzchołków to graf postaci <center><math>\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), </math></center>
*  '''iloraz''' grafu <math>\mathbf{G}</math> przez relację równoważności  
+
*  '''ściągnięcie''' zbioru wierzchołków <math>X\subseteq V</math> w grafie <math>\mathbf{G}</math> to szczególny przypadek ilorazu <math>\mathbf{G}/\theta</math>, w którym  klasy równoważności wszystkich wierzchołków spoza <math>X</math> są jednoelementowe, a <math>X</math> stanowi dodatkową klasę, tzn. <math>V/\theta=\left\lbrace \left\lbrace v \right\rbrace:v\in V- X \right\rbrace\cup\left\lbrace X \right\rbrace</math>. W ten sposób zbiór <math>X</math> został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z <math>X</math>. Z drugiej strony, jeśli <math>\theta\subseteq V\times V</math> jest relacją równoważności o klasach <math>X_1,\ldots,X_k</math>, to ściągając w grafie <math>\mathbf{G}</math> kolejno zbiory <math>X_1,\ldots,X_k</math> otrzymamy graf ilorazowy <math>\mathbf{G}/\theta</math>.
<math>\theta\subseteq V\times V</math>
 
na zbiorze jego wierzchołków to graf postaci
 
 
 
<center><math>\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),
 
</math></center>
 
 
 
*  '''ściągnięcie''' zbioru wierzchołków <math>X\subseteq V</math> w grafie <math>\mathbf{G}</math>  
 
to szczególny przypadek ilorazu <math>\mathbf{G}/\theta</math>,  
 
w którym  klasy równoważności wszystkich wierzchołków spoza <math>X</math> są jednoelementowe,  
 
a <math>X</math> stanowi dodatkową klasę, tzn.
 
<math>V/\theta=\left\lbrace \left\lbrace v \right\rbrace:v\in V- X \right\rbrace\cup\left\lbrace X \right\rbrace</math>.  
 
W ten sposób zbiór <math>X</math> został ściągnięty do punktu, którego sąsiadami są  
 
sąsiedzi jakiegokolwiek wierzchołka z <math>X</math>.
 
Z drugiej strony, jeśli <math>\theta\subseteq V\times V</math> jest relacją równoważności  
 
o klasach <math>X_1,\ldots,X_k</math>, to ściągając w grafie <math>\mathbf{G}</math> kolejno zbiory  
 
<math>X_1,\ldots,X_k</math> otrzymamy graf ilorazowy <math>\mathbf{G}/\theta</math>.
 
  
 
Dowód charakteryzacji grafów planarnych w terminach ściągalności również pomijamy.
 
Dowód charakteryzacji grafów planarnych w terminach ściągalności również pomijamy.
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|3||
  
 
Graf jest planarny wtedy i tylko wtedy,  
 
Graf jest planarny wtedy i tylko wtedy,  
Linia 121: Linia 84:
 
}}
 
}}
  
{{przyklad|[Uzupelnij]||
+
{{przyklad|||
  
 
W grafie przedstawionym na rysunku [[##pict sciagalny k33|Uzupelnic pict sciagalny k33|]] ściągnięcie  
 
W grafie przedstawionym na rysunku [[##pict sciagalny k33|Uzupelnic pict sciagalny k33|]] ściągnięcie  
Linia 128: Linia 91:
 
A więc, na mocy  Twierdzenia [[##th ściągalny k5k33|Uzupelnic th ściągalny k5k33|]],  
 
A więc, na mocy  Twierdzenia [[##th ściągalny k5k33|Uzupelnic th ściągalny k5k33|]],  
 
graf ten nie jest planarny.  
 
graf ten nie jest planarny.  
 
[!h]
 
  
 
{grafy_sciagalny_k33}
 
{grafy_sciagalny_k33}
Linia 144: Linia 105:
 
Innym słowy ściana to zbiór punktów płaszczyzny,  
 
Innym słowy ściana to zbiór punktów płaszczyzny,  
 
które da się połączyć krzywą nieprzecinającą żadnej krawędzi.
 
które da się połączyć krzywą nieprzecinającą żadnej krawędzi.
 
[!h]
 
  
 
{grafy_sciany}
 
{grafy_sciany}
Linia 161: Linia 120:
 
(tzn. spójnych składowych) w lesie.
 
(tzn. spójnych składowych) w lesie.
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|4 [Euler 1750]||
[Euler 1750]
 
  
 
W grafie płaskim <math>\mathbf{G}=\left( V,E \right)</math>  
 
W grafie płaskim <math>\mathbf{G}=\left( V,E \right)</math>  
 
o <math>f</math> ścianach i <math>k\geq 1</math> składowych spójnych zachodzi  
 
o <math>f</math> ścianach i <math>k\geq 1</math> składowych spójnych zachodzi  
 
 
<center><math>\left\vert V \right\vert-\left\vert E \right\vert+f=k+1.
 
<center><math>\left\vert V \right\vert-\left\vert E \right\vert+f=k+1.
 
</math></center>
 
</math></center>
Linia 172: Linia 129:
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Dowód poprowadzimy indukcją ze względu na liczbę krawędzi.  
 
Dowód poprowadzimy indukcją ze względu na liczbę krawędzi.  
Linia 193: Linia 150:
 
}}
 
}}
  
{{uwaga|[Uzupelnij]||
+
{{uwaga|||
  
 
Ważną konsekwencją Twierdzenia [[##th ilość krawędzi|Uzupelnic th ilość krawędzi|]] jest to,  
 
Ważną konsekwencją Twierdzenia [[##th ilość krawędzi|Uzupelnic th ilość krawędzi|]] jest to,  
Linia 204: Linia 161:
 
pozostawiamy jako ćwiczenie.
 
pozostawiamy jako ćwiczenie.
  
{{wniosek|[Uzupelnij]||
+
{{wniosek|5||
  
 
Jeśli <math>\mathbf{G}=\left( V,E \right)</math> jest spójnym grafem planarnym o co najmniej <math>3</math> wierzchołkach, to
 
Jeśli <math>\mathbf{G}=\left( V,E \right)</math> jest spójnym grafem planarnym o co najmniej <math>3</math> wierzchołkach, to
 
 
<center><math>\left\vert E \right\vert\leq 3\left\vert V \right\vert-6.
 
<center><math>\left\vert E \right\vert\leq 3\left\vert V \right\vert-6.
 
</math></center>
 
</math></center>
Linia 213: Linia 169:
 
}}
 
}}
  
{{wniosek|[Uzupelnij]||
+
{{wniosek|6||
 
Spójny graf planarny o <math>\left\vert V \right\vert\geq1</math> posiada wierzchołek o stopniu nie większym niż <math>5</math>.
 
Spójny graf planarny o <math>\left\vert V \right\vert\geq1</math> posiada wierzchołek o stopniu nie większym niż <math>5</math>.
 
}}
 
}}
  
 
'''Graf dualny geometrycznie''' do grafu płaskiego <math>\mathbf{G}=\left( V,E \right)</math> to graf płaski <math>\mathbf{G}^*=\left( V^*,E^* \right)</math> skonstruowany w następujący sposób:
 
'''Graf dualny geometrycznie''' do grafu płaskiego <math>\mathbf{G}=\left( V,E \right)</math> to graf płaski <math>\mathbf{G}^*=\left( V^*,E^* \right)</math> skonstruowany w następujący sposób:
 
 
* Z każdej ściany grafu <math>\mathbf{G}</math> wybieramy po jednym punkcie. Tak wybrane punkty tworzą zbiór wierzchołków <math>V^*</math>.
 
* Z każdej ściany grafu <math>\mathbf{G}</math> wybieramy po jednym punkcie. Tak wybrane punkty tworzą zbiór wierzchołków <math>V^*</math>.
 
 
* Jeśli krawędź po jednej stronie sąsiadowała ze ścianą <math>f_1</math>, a po drugiej z <math>f_2</math> to w grafie <math>\mathbf{G}^*</math> odpowiadające ścianom <math>f_1,f_2</math> wierzchołki <math>v_1^*,v_2^*</math> łączymy krawędzią <math>v_1^*v_2^*</math>. Tak wybrane krawędzie tworzą zbiór <math>E^*</math>.
 
* Jeśli krawędź po jednej stronie sąsiadowała ze ścianą <math>f_1</math>, a po drugiej z <math>f_2</math> to w grafie <math>\mathbf{G}^*</math> odpowiadające ścianom <math>f_1,f_2</math> wierzchołki <math>v_1^*,v_2^*</math> łączymy krawędzią <math>v_1^*v_2^*</math>. Tak wybrane krawędzie tworzą zbiór <math>E^*</math>.
 
[!h]
 
  
 
{grafy_dualny}
 
{grafy_dualny}
 
{Graf (w kolorze czarnym) oraz graf do niego dualny geometrycznie (w kolorze turkusowym). '''[Rysunek z pliku:''' <tt>grafydualny.eps</tt>''']'''}
 
{Graf (w kolorze czarnym) oraz graf do niego dualny geometrycznie (w kolorze turkusowym). '''[Rysunek z pliku:''' <tt>grafydualny.eps</tt>''']'''}
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|7||
  
 
Jeśli <math>\mathbf{G}</math> jest spójnym grafem płaskim,  
 
Jeśli <math>\mathbf{G}</math> jest spójnym grafem płaskim,  
Linia 234: Linia 186:
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Każda ściana grafu <math>\mathbf{G}^{*}</math> reprezentowana jest  
 
Każda ściana grafu <math>\mathbf{G}^{*}</math> reprezentowana jest  
Linia 251: Linia 203:
 
}}
 
}}
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|8||
  
 
Niech <math>\mathbf{G}^*</math> będzie grafem geometrycznie dualnym do  
 
Niech <math>\mathbf{G}^*</math> będzie grafem geometrycznie dualnym do  
Linia 260: Linia 212:
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Niech <math>C</math> będzie cyklem w grafie <math>\mathbf{G}</math>.
 
Niech <math>C</math> będzie cyklem w grafie <math>\mathbf{G}</math>.
Linia 280: Linia 232:
 
Tak więc, zbiór <math>C^*</math> krawędzi dualnych do krawędzi z cyklu <math>C</math>  
 
Tak więc, zbiór <math>C^*</math> krawędzi dualnych do krawędzi z cyklu <math>C</math>  
 
tworzy zbiór rozspajający wierzchołki <math>v_1^*,v_0^*</math>.  
 
tworzy zbiór rozspajający wierzchołki <math>v_1^*,v_0^*</math>.  
 
[!h]
 
  
 
{grafy_cykl_rozc}
 
{grafy_cykl_rozc}
Linia 323: Linia 273:
 
'''Optymalne kolorowanie''' grafu <math>\mathbf{G}</math> to kolorowanie używające  
 
'''Optymalne kolorowanie''' grafu <math>\mathbf{G}</math> to kolorowanie używające  
 
dokładnie <math>\chi\!\left( \mathbf{G} \right)</math> kolorów.  
 
dokładnie <math>\chi\!\left( \mathbf{G} \right)</math> kolorów.  
 
[!h]
 
  
 
{grafy_kolorowanie}
 
{grafy_kolorowanie}
 
{Kolorowanie grafu nieoptymalne (a), optymalne (b) oraz niepoprawne (c) '''[Rysunek z pliku:''' <tt>grafykolorowanie.eps</tt>''']'''}
 
{Kolorowanie grafu nieoptymalne (a), optymalne (b) oraz niepoprawne (c) '''[Rysunek z pliku:''' <tt>grafykolorowanie.eps</tt>''']'''}
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|9||
  
 
Graf, którego wszystkie wierzchołki mają stopień nie większy niż <math>k</math>
 
Graf, którego wszystkie wierzchołki mają stopień nie większy niż <math>k</math>
Linia 335: Linia 283:
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Dowód poprowadzimy indykcyjnie ze względu na liczbę wierzchołków w grafie  
 
Dowód poprowadzimy indykcyjnie ze względu na liczbę wierzchołków w grafie  
Linia 357: Linia 305:
 
ale podajemy je bez dowodu.
 
ale podajemy je bez dowodu.
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|10 [Brooks 1941]||
[Brooks 1941]
 
 
Niech <math>\mathbf{G}</math> będzie spójnym grafem prostym, który nie jest kliką.  
 
Niech <math>\mathbf{G}</math> będzie spójnym grafem prostym, który nie jest kliką.  
 
Jeśli wszystkie wierzchołki grafu <math>\mathbf{G}</math> mają stopień nie większy niż <math>k</math>  
 
Jeśli wszystkie wierzchołki grafu <math>\mathbf{G}</math> mają stopień nie większy niż <math>k</math>  
Linia 367: Linia 314:
 
powiedzieć więcej o ich liczbie chromatycznej.
 
powiedzieć więcej o ich liczbie chromatycznej.
  
{{obserwacje|[Uzupelnij]||
+
{{obserwacje|11||
  
 
Graf jest dwudzielny wtedy i tylko wtedy, gdy jest <math>2</math>-kolorowalny.  
 
Graf jest dwudzielny wtedy i tylko wtedy, gdy jest <math>2</math>-kolorowalny.  
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Zauważmy najpierw, że w grafie dwudzielnym <math>\mathbf{G}=\left( V_1\cup V_2,E \right)</math>,   
 
Zauważmy najpierw, że w grafie dwudzielnym <math>\mathbf{G}=\left( V_1\cup V_2,E \right)</math>,   
Linia 382: Linia 329:
 
}}
 
}}
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|12||
  
 
Każdy graf planarny jest <math>5</math>-kolorowalny.
 
Każdy graf planarny jest <math>5</math>-kolorowalny.
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków
 
Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków
Linia 408: Linia 355:
 
Bez straty ogólności ich ułożenie może wyglądać  
 
Bez straty ogólności ich ułożenie może wyglądać  
 
jak na rysunku [[##pict grafy 5barw planar|Uzupelnic pict grafy 5barw planar|]].
 
jak na rysunku [[##pict grafy 5barw planar|Uzupelnic pict grafy 5barw planar|]].
 
[!h]
 
  
 
{grafy_5barw_planar}
 
{grafy_5barw_planar}
Linia 427: Linia 372:
 
W efekcie otrzymujemy cykl <math>v\to v_1\to R\to v_3\to v</math>,  
 
W efekcie otrzymujemy cykl <math>v\to v_1\to R\to v_3\to v</math>,  
 
który ogranicza obszar zawierający wierzchołek <math>v_2</math> i nie zawierający <math>v_4</math>.
 
który ogranicza obszar zawierający wierzchołek <math>v_2</math> i nie zawierający <math>v_4</math>.
 
[!h]
 
  
 
{grafy_5barw_planar2}
 
{grafy_5barw_planar2}
Linia 445: Linia 388:
 
Dowód ten pomijamy.
 
Dowód ten pomijamy.
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|13||
  
 
Każdy graf planarny jest <math>4</math>-kolorowalny.
 
Każdy graf planarny jest <math>4</math>-kolorowalny.
Linia 460: Linia 403:
 
jeśli jej geometrycznie dualny graf <math>\mathbf{M}^*</math> jest <math>k</math> kolorowalny.
 
jeśli jej geometrycznie dualny graf <math>\mathbf{M}^*</math> jest <math>k</math> kolorowalny.
  
{{twierdzenie|[Uzupelnij]||
+
{{twierdzenie|14||
  
 
Mapa <math>\mathbf{M}</math> ma <math>2</math>-kolorowalne ściany
 
Mapa <math>\mathbf{M}</math> ma <math>2</math>-kolorowalne ściany
Linia 466: Linia 409:
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Załóżmy najpierw, że ściany są pomalowane dwoma kolorami.
 
Załóżmy najpierw, że ściany są pomalowane dwoma kolorami.
Linia 495: Linia 438:
 
dostajemy natychmiast następujący wniosek.
 
dostajemy natychmiast następujący wniosek.
  
{{wniosek|[Uzupelnij]||
+
{{wniosek|15||
  
 
Każda mapa ma  <math>4</math>-kolorowalne ściany.
 
Każda mapa ma  <math>4</math>-kolorowalne ściany.
Linia 506: Linia 449:
 
'''Liczba stopniowa grafu.'''  
 
'''Liczba stopniowa grafu.'''  
 
Niech <math>\mathbf{G}=\left( \left\lbrace v_1,\ldots,v_n \right\rbrace,E \right)</math> będzie grafem prostym.  
 
Niech <math>\mathbf{G}=\left( \left\lbrace v_1,\ldots,v_n \right\rbrace,E \right)</math> będzie grafem prostym.  
Przy każdej permutacji <math>\rho:\left\lbrace 1,\ldots,n \right\rbrace\longrightarrow\left\lbrace 1,\ldots,n \right\rbrace</math>  
+
Przy każdej permutacji <math>\rho:\left\lbrace 1,\ldots,n \right\rbrace\longrightarrow\left\lbrace 1,\ldots,n \right\rbrace</math> każdemu wierzchołkowi <math>v_{\rho\left( i \right)}</math> przypisana jest liczba sąsiadów  
każdemu wierzchołkowi <math>v_{\rho\left( i \right)}</math> przypisana jest liczba sąsiadów  
 
 
<math>n_{\rho\left( i \right)}^{\rho}</math> w zbiorze wierzchołków o indeksie mniejszym niż <math>\rho\left( i \right)</math>.  
 
<math>n_{\rho\left( i \right)}^{\rho}</math> w zbiorze wierzchołków o indeksie mniejszym niż <math>\rho\left( i \right)</math>.  
 
Liczba stopniowa jest równa
 
Liczba stopniowa jest równa
 
 
<center><math>\chi_s\!\left( \mathbf{G} \right)= \min_{\rho}\max_{i=1,\ldots, n}{n_i^{\rho}}.
 
<center><math>\chi_s\!\left( \mathbf{G} \right)= \min_{\rho}\max_{i=1,\ldots, n}{n_i^{\rho}}.
 
</math></center>
 
</math></center>
  
{{przyklad|[Uzupelnij]||
+
{{przyklad|||
  
 
Rozważmy graf <math>\mathbf{G}_1=\left( \left\lbrace v_1,v_2,v_3,v_4,v_5 \right\rbrace,E \right)</math>  
 
Rozważmy graf <math>\mathbf{G}_1=\left( \left\lbrace v_1,v_2,v_3,v_4,v_5 \right\rbrace,E \right)</math>  
 
przedstawiony na rysunku [[##grafy liczba stopniowa 1|Uzupelnic grafy liczba stopniowa 1|]].
 
przedstawiony na rysunku [[##grafy liczba stopniowa 1|Uzupelnic grafy liczba stopniowa 1|]].
 
[!h]
 
  
 
{grafy_liczba_stopniowa_1}
 
{grafy_liczba_stopniowa_1}
Linia 544: Linia 483:
 
<math>\displaystyle{\min_{\rho}\max_{i=1,\ldots, n}{n_i^{\rho}}}</math>,  
 
<math>\displaystyle{\min_{\rho}\max_{i=1,\ldots, n}{n_i^{\rho}}}</math>,  
 
a zatem <math>\chi_s\!\left( \mathbf{G} \right)=2</math>.
 
a zatem <math>\chi_s\!\left( \mathbf{G} \right)=2</math>.
 
[!h]
 
  
 
{grafy_liczba_stopniowa_2}
 
{grafy_liczba_stopniowa_2}
Linia 555: Linia 492:
 
nadajemy im kolor niewykorzystany dla żadnego dotąd rozpatrywanego sąsiada.  
 
nadajemy im kolor niewykorzystany dla żadnego dotąd rozpatrywanego sąsiada.  
 
Otrzymujemy wtedy kolorowanie przedstawione na rysunku [[##grafy liczba stopniowa 3|Uzupelnic grafy liczba stopniowa 3|]].
 
Otrzymujemy wtedy kolorowanie przedstawione na rysunku [[##grafy liczba stopniowa 3|Uzupelnic grafy liczba stopniowa 3|]].
 
[!h]
 
  
 
{grafy_liczba_stopniowa_3}
 
{grafy_liczba_stopniowa_3}
Linia 565: Linia 500:
 
Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.  
 
Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.  
  
{{obserwacje|[Uzupelnij]||
+
{{obserwacje|16||
  
 
Jeżeli <math>\mathbf{G}</math> jest grafem prostym, to
 
Jeżeli <math>\mathbf{G}</math> jest grafem prostym, to
 
 
<center><math>\chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1.
 
<center><math>\chi\!\left( \mathbf{G} \right)\leq\chi_s\!\left( \mathbf{G} \right)+1.
 
</math></center>
 
</math></center>
Linia 574: Linia 508:
 
}}
 
}}
  
{{dowod|[Uzupelnij]||
+
{{dowod|||
  
 
Niech <math>v_1,\ldots,v_n</math> będzie ciągiem wierzchołków grafu <math>\mathbf{G}</math>  
 
Niech <math>v_1,\ldots,v_n</math> będzie ciągiem wierzchołków grafu <math>\mathbf{G}</math>  

Wersja z 20:16, 21 sie 2006

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