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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 92 wersji utworzonych przez 6 użytkowników)
Linia 1: Linia 1:
 
==Grafy planarne==
 
==Grafy planarne==
 +
 
 +
[[File:Grafy planarne.mp4|250x250px|thumb|left|Graf nieplanarny (a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c)]]
  
'''Graf płaski''' to para:  
+
[[File:Grafy k33.svg|200x200px|thumb|right|Grafy k33]]
<math>\mathbf{\overline{G}}=\left( \overline{V},\overline{E} \right)</math>, gdzie
+
 
 +
[[File:Grafy k332.svg|200x200px|thumb|right|Grafy k332]]
 +
 
 +
'''Graf płaski''' to para: <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 w 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.
  
{grafy_planarne}
+
{{obserwacja|14.1|obs 14.1|
{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|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|||
 
{{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 rysunek[[#Grafy k33|Grafy k33]].
 
 
{grafy_k33}
 
{ '''[Rysunek z pliku:''' <tt>grafyk33.eps</tt>''']'''}
 
  
 
Spośród krawędzi <math>v_1 v_4</math> i <math>v_2 v_5</math> jedna musi  leżeć wewnątrz cyklu  
 
Spośród krawędzi <math>v_1 v_4</math> i <math>v_2 v_5</math> jedna musi  leżeć wewnątrz cyklu  
Linia 30: Linia 26:
 
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>.
 
{grafy_k332}
 
{ '''[Rysunek z pliku:''' <tt>grafyk332.eps</tt>''']'''}
 
  
 
Dowód dla <math>\mathcal{K}_{5}</math> jest analogiczny,  
 
Dowód dla <math>\mathcal{K}_{5}</math> jest analogiczny,  
Linia 38: Linia 31:
 
}}
 
}}
  
Z Obserwacji [[##th k5 i k33 nieplanarne|Uzupelnic th k5 i k33 nieplanarne|]] natychmiast wynika,  
+
Z [[#obs_14.1|Obserwacji 14.1]] natychmiast wynika,  
 
ż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  
Linia 46: Linia 39:
 
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>.
+
* Dodawanie wierzchołków stopnia dwa na krawędzi.<br> Jeśli <math>uw\in\mathsf{ E}\!\left(\mathbf{G}_1\right)</math> oraz <math>x\not\in\mathsf{ V}\!\left(\mathbf{G}_1\right)</math>, to operacja ta zastępuje graf <math>\left( \mathsf{ V}\!\left(\mathbf{G}_1\right),\mathsf{ E}\!\left(\mathbf{G}_1\right) \right)</math> grafem <math>\left( \mathsf{ V}\!\left(\mathbf{G}_1\right)\cup\left\lbrace x \right\rbrace,\mathsf{ 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>.
+
* Usuwanie wierzchołków stopnia dwa.<br>Jeśli <math>x\in\mathsf{ 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( \mathsf{ V}\!\left(\mathbf{G}_1\right),\mathsf{ E}\!\left(\mathbf{G}_1\right) \right)</math> grafem <math>\left( \mathsf{ V}\!\left(\mathbf{G}_1\right)-\left\lbrace x \right\rbrace,\mathsf{ E}\!\left(\mathbf{G}_1\right)\cup\left\lbrace uw \right\rbrace-\left\lbrace ux,xw \right\rbrace \right)</math>.
 +
 
 +
{{kotwica|Grafy homeomorficzne||}}
 +
[[File:Grafy homeomorficzne.svg|250x100px|thumb|left|Grafy homeomorficzne]]
  
 
{{przyklad|||
 
{{przyklad|||
 
+
Grafy <math>\mathbf{G},\mathbf{G}'</math> przedstawione na rysunku [[#Grafy homeomorficzne|Grafy homeomorficzne]]  
Grafy <math>\mathbf{G},\mathbf{G}'</math> przedstawione na rysunku [[##pict homeomorficzne|Uzupelnic pict homeomorficzne|]]  
 
 
są ze sobą homeomorficzne,  
 
są ze sobą homeomorficzne,  
 
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>.  
 
{grafy_homeomorficzne}
 
{ '''[Rysunek z pliku:''' <tt>grafyhomeomorficzne.eps</tt>''']'''}
 
  
 
}}
 
}}
Linia 64: Linia 56:
 
Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.
 
Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.
  
{{twierdzenie|2 [Kuratowski 1930]||
+
{{twierdzenie|14.2 [Kuratowski 1930]|tw 14.2|
 
 
 
Graf jest planarny wtedy i tylko wtedy,  
 
Graf jest planarny wtedy i tylko wtedy,  
 
gdy żaden jego podgraf nie jest homeomorficzny z <math>\mathcal{K}_{5}</math> ani z <math>\mathcal{K}_{3,3}</math>.  
 
gdy żaden jego podgraf nie jest homeomorficzny z <math>\mathcal{K}_{5}</math> ani z <math>\mathcal{K}_{3,3}</math>.  
Linia 73: Linia 64:
 
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 <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>.
 
*  '''ś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.
 +
{{kotwica||Grafy sciagalne k33||}}
 +
<div class="thumb tleft"><div style="width:250px;"> 
 +
<flashwrap>file=Grafy sciagalne k33.swf|size=small</flashwrap> 
 +
<div.thumbcaption>Graf posiadający podgraf ściągalny do <math>\mathcal{K}_{3,3}</math></div></div> 
 +
</div>
 +
{{kotwica|Grafy sciany||}}
 +
[[File:Grafy sciany.svg|250x250px|thumb|right|Graf posiadający cztery ściany: <math>f_0, f_1,f_2,f_3</math>]]
  
{{twierdzenie|3||
+
{{twierdzenie|14.3|tw_14.3|
 
 
 
Graf jest planarny wtedy i tylko wtedy,  
 
Graf jest planarny wtedy i tylko wtedy,  
 
gdy nie zawiera podgrafu ściągalnego do <math>\mathcal{K}_{5}</math> lub <math>\mathcal{K}_{3,3}</math>.
 
gdy nie zawiera podgrafu ściągalnego do <math>\mathcal{K}_{5}</math> lub <math>\mathcal{K}_{3,3}</math>.
Linia 85: Linia 85:
  
 
{{przyklad|||
 
{{przyklad|||
 
+
W grafie przedstawionym na rysunku [[#Grafy sciagalne k33|Grafy ściagalne k33]] ściągnięcie  
W grafie przedstawionym na rysunku [[##pict sciagalny k33|Uzupelnic pict sciagalny k33|]] ściągnięcie  
 
 
zbiorów wierzchołków otoczonych przerywaną linią prowadzi do  
 
zbiorów wierzchołków otoczonych przerywaną linią prowadzi do  
 
grafu zawierającego <math>\mathcal{K}_{3,3}</math>.  
 
grafu zawierającego <math>\mathcal{K}_{3,3}</math>.  
A więc, na mocy Twierdzenia [[##th ściągalny k5k33|Uzupelnic th ściągalny k5k33|]],  
+
A więc, na mocy [[#tw_14.3| Twierdzenia 14.3]],  
 
graf ten nie jest planarny.  
 
graf ten nie jest planarny.  
 
{grafy_sciagalny_k33}
 
{Graf posiadający podgraf ściągalny do <math>\mathcal{K}_{3,3}</math>. '''[Rysunek z pliku:''' <tt>grafysciagalnyk33.eps</tt>''']'''}
 
  
 
}}
 
}}
Linia 102: Linia 98:
 
'''Ściana''' w grafie płaskim <math>\mathbf{G}</math> to spójny obszar  
 
'''Ściana''' w grafie płaskim <math>\mathbf{G}</math> to spójny obszar  
 
płaszczyzny po usunięciu linii reprezentujących krawędzie, tzn.  
 
płaszczyzny po usunięciu linii reprezentujących krawędzie, tzn.  
<math>R^2-\bigcup{\sf E}\!\left(\mathbf{G}\right)</math>.
+
<math>R^2-\bigcup\mathsf{ E}\!\left(\mathbf{G}\right)</math>.
 
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.
  
{grafy_sciany}
+
Ściana <math>f_0</math> w grafie z rysunku [[#Grafy sciany|Graf o czterech ścianach]] jest ścianą nieograniczoną,  
{Graf posiadający cztery ściany: <math>f_0, f_1,f_2,f_3</math>. '''[Rysunek z pliku:''' <tt>grafysciany.eps</tt>''']'''}
 
 
 
Ściana <math>f_0</math> w grafie z rysunku [[##pict ściana|Uzupelnic pict ściana|]] jest ścianą nieograniczoną,  
 
 
która nazywana jest też ''ścianą nieskończoną''.  
 
która nazywana jest też ''ścianą nieskończoną''.  
 
Nie tylko ten graf, ale wszystkie grafy płaskie  
 
Nie tylko ten graf, ale wszystkie grafy płaskie  
Linia 120: Linia 113:
 
(tzn. spójnych składowych) w lesie.
 
(tzn. spójnych składowych) w lesie.
  
{{twierdzenie|4 [Euler 1750]||
+
{{twierdzenie|14.4 [Euler 1750]|tw 14.4|
 +
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
 +
 
 +
 
 +
<center>
 +
<math>\left\vert V \right\vert-\left\vert E \right\vert+f=k+1.
 +
</math>
 +
</center>
  
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
 
<center><math>\left\vert V \right\vert-\left\vert E \right\vert+f=k+1.
 
</math></center>
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
 
Dowód poprowadzimy indukcją ze względu na liczbę krawędzi.  
 
Dowód poprowadzimy indukcją ze względu na liczbę krawędzi.  
 
Jeżeli graf <math>\mathbf{G}</math> jest pusty to <math>\left\vert E \right\vert=0,k=\left\vert V \right\vert,\ f=1</math>,  
 
Jeżeli graf <math>\mathbf{G}</math> jest pusty to <math>\left\vert E \right\vert=0,k=\left\vert V \right\vert,\ f=1</math>,  
Linia 151: Linia 147:
  
 
{{uwaga|||
 
{{uwaga|||
 
+
Ważną konsekwencją [[#tw_14.4|Twierdzenia 14.4]] jest to,  
Ważną konsekwencją Twierdzenia [[##th ilość krawędzi|Uzupelnic th ilość krawędzi|]] jest to,  
 
 
że liczba ścian zależy jedynie od liczby wierzchołków, krawędzi,  
 
że liczba ścian zależy jedynie od liczby wierzchołków, krawędzi,  
 
oraz spójnych składowych.   
 
oraz spójnych składowych.   
Linia 158: Linia 153:
 
}}
 
}}
  
Uzasadnienie dwu kolejnych wniosków z Twierdzenia [[##th ilość krawędzi|Uzupelnic th ilość krawędzi|]]  
+
Uzasadnienie dwu kolejnych wniosków z [[#tw_14.4|Twierdzenia 14.4]]  
 
pozostawiamy jako ćwiczenie.
 
pozostawiamy jako ćwiczenie.
  
{{wniosek|5||
+
{{wniosek|14.5|wn 14.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>
 +
  
 
}}
 
}}
  
{{wniosek|6||
+
{{wniosek|14.6|wn 14.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>.
 
}}
 
}}
 +
{{kotwica|Grafy dualny||}}
 +
[[File:Grafy dualny.svg|250x250px|thumb|right|Graf (w kolorze czerwono-niebieskim) oraz graf do niego dualny geometrycznie (w kolorze żółto-szarym)]]
  
 
'''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:
Linia 177: Linia 176:
 
* 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>.
  
{grafy_dualny}
+
{{twierdzenie|14.7|tw 14.7|
{Graf (w kolorze czarnym) oraz graf do niego dualny geometrycznie (w kolorze turkusowym). '''[Rysunek z pliku:''' <tt>grafydualny.eps</tt>''']'''}
 
 
 
{{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,  
 
to <math>\mathbf{G}^{**}</math> jest izomorficzny z <math>\mathbf{G}</math>.
 
to <math>\mathbf{G}^{**}</math> jest izomorficzny z <math>\mathbf{G}</math>.
Linia 187: Linia 182:
  
 
{{dowod|||
 
{{dowod|||
 
 
Każda ściana grafu <math>\mathbf{G}^{*}</math> reprezentowana jest  
 
Każda ściana grafu <math>\mathbf{G}^{*}</math> reprezentowana jest  
 
jednym wierzchołkiem <math>\mathbf{G}^{**}</math>.
 
jednym wierzchołkiem <math>\mathbf{G}^{**}</math>.
Linia 203: Linia 197:
 
}}
 
}}
  
{{twierdzenie|8||
+
{{twierdzenie|14.8|tw 14.8|
 
 
 
Niech <math>\mathbf{G}^*</math> będzie grafem geometrycznie dualnym do  
 
Niech <math>\mathbf{G}^*</math> będzie grafem geometrycznie dualnym do  
 
grafu płaskiego <math>\mathbf{G}</math>.
 
grafu płaskiego <math>\mathbf{G}</math>.
Linia 211: Linia 204:
 
jest rozcięciem grafu <math>\mathbf{G}^*</math>.
 
jest rozcięciem grafu <math>\mathbf{G}^*</math>.
 
}}
 
}}
 +
{{kotwica|Grafy cykl rozC||}}
 +
[[File:Grafy cykl rozC.svg|250x250px|thumb|right|Grafy cykl rozC]]
  
 
{{dowod|||
 
{{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>.
 
W grafie płaskim cykl dzieli płaszczyznę <math>\mathbb{R}^2</math>  
 
W grafie płaskim cykl dzieli płaszczyznę <math>\mathbb{R}^2</math>  
Linia 232: Linia 226:
 
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>.  
 
{grafy_cykl_rozc}
 
{ '''[Rysunek z pliku:''' <tt>grafycyklrozc.eps</tt>''']'''}
 
  
 
Pokażemy, że zbiór <math>C^*</math> jest rozcięciem, czyli minimalnym zbiorem rozspajającym.
 
Pokażemy, że zbiór <math>C^*</math> jest rozcięciem, czyli minimalnym zbiorem rozspajającym.
Linia 248: Linia 239:
 
}}
 
}}
  
==Kolorowanie grafów.==
+
==Kolorowanie grafów==
  
 
W tej części wykładu zajmiemy się problemami związanymi z kolorowaniem 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  
 
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
+
każde dwa sąsiednie wierzchołki miały różne kolory.
  
 
'''Kolorowanie''' grafu <math>\mathbf{G}=\left( V,E \right)</math>  
 
'''Kolorowanie''' grafu <math>\mathbf{G}=\left( V,E \right)</math>  
Linia 264: Linia 255:
 
Na odwrót, rozbicie <math>V = V_0\cup V_1\cup\ldots\cup V_{k-1}</math>  
 
Na odwrót, rozbicie <math>V = V_0\cup V_1\cup\ldots\cup V_{k-1}</math>  
 
pozwala na pokolorowanie grafu <math>\mathbf{G}</math> na <math>k</math> kolorów.
 
pozwala na pokolorowanie grafu <math>\mathbf{G}</math> na <math>k</math> kolorów.
 +
{{kotwica|Kolorowanie grafu||}}
 +
[[File:Grafy kolorowanie.svg|350x250px|thumb|right|Kolorowanie grafu nieoptymalne (a), optymalne (b) oraz niepoprawne (c)]]
  
 
'''Graf <math>k</math>-kolorowalny''' (<math>k</math>-barwny)  
 
'''Graf <math>k</math>-kolorowalny''' (<math>k</math>-barwny)  
Linia 274: Linia 267:
 
dokładnie <math>\chi\!\left( \mathbf{G} \right)</math> kolorów.  
 
dokładnie <math>\chi\!\left( \mathbf{G} \right)</math> kolorów.  
  
{grafy_kolorowanie}
+
{{twierdzenie|14.9|tw_14.9|
{Kolorowanie grafu nieoptymalne (a), optymalne (b) oraz niepoprawne (c) '''[Rysunek z pliku:''' <tt>grafykolorowanie.eps</tt>''']'''}
 
 
 
{{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>
 
jest <math>(k+1)</math>-kolorowalny.
 
jest <math>(k+1)</math>-kolorowalny.
Linia 284: Linia 273:
  
 
{{dowod|||
 
{{dowod|||
 
+
Dowód poprowadzimy indukcyjnie ze względu na liczbę wierzchołków w grafie  
Dowód poprowadzimy indykcyjnie ze względu na liczbę wierzchołków w grafie  
 
 
<math>\mathbf{G}=\left( V,E \right)</math>.  
 
<math>\mathbf{G}=\left( V,E \right)</math>.  
 
Jeśli graf ma jeden wierzchołek, to oczywiście wystarcza jeden kolor.
 
Jeśli graf ma jeden wierzchołek, to oczywiście wystarcza jeden kolor.
Linia 299: Linia 287:
  
 
Ograniczenia górnego, na liczbę chromatyczną grafu,  
 
Ograniczenia górnego, na liczbę chromatyczną grafu,  
podanego w Twierdzeniu [[##th rho plus 1|Uzupelnic th rho plus 1|]] nie można w ogólności wzmocnić.
+
podanego w [[#tw_14.9|Twierdzeniu 14.9]] nie można w ogólności wzmocnić.
 
Istotnie, każde kolorowanie kliki <math>\mathcal{K}_{k+1}</math> wymaga dokładnie <math>k+1</math> kolorów,  
 
Istotnie, każde kolorowanie kliki <math>\mathcal{K}_{k+1}</math> wymaga dokładnie <math>k+1</math> kolorów,  
 
mimo iż stopień każdego wierzchołka to <math>k</math>.
 
mimo iż stopień każdego wierzchołka to <math>k</math>.
Następne twierdzenie wzmacnia jednak znacznie twierdzenia [[##th rho plus 1|Uzupelnic th rho plus 1|]],  
+
Następne twierdzenie wzmacnia jednak znacznie [[#tw_14.9|Twierdzenia 14.9]],  
 
ale podajemy je bez dowodu.
 
ale podajemy je bez dowodu.
  
{{twierdzenie|10 [Brooks 1941]||
+
{{twierdzenie|14.10 [Brooks 1941]|tw 14.10|
 
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 314: Linia 302:
 
powiedzieć więcej o ich liczbie chromatycznej.
 
powiedzieć więcej o ich liczbie chromatycznej.
  
{{obserwacje|11||
+
{{obserwacja|14.11|obs 14.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|||
 
{{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>,   
 
podgrafy indukowane <math>\mathbf{G}|_{V_1}</math> oraz <math>\mathbf{G}|_{V_2}</math> są antyklikami.
 
podgrafy indukowane <math>\mathbf{G}|_{V_1}</math> oraz <math>\mathbf{G}|_{V_2}</math> są antyklikami.
Linia 329: Linia 315:
 
}}
 
}}
  
{{twierdzenie|12||
+
{{twierdzenie|14.12|tw 14.12|
 
 
 
Każdy graf planarny jest <math>5</math>-kolorowalny.
 
Każdy graf planarny jest <math>5</math>-kolorowalny.
 
}}
 
}}
 +
 +
{{kotwica|Grafy 5barw planar||}}
 +
[[File:Grafy 5barw planar.svg|250x250px|thumb|left|Grafy 5barw planar]]
 +
 +
{{kotwica|Grafy 5barw planar2||}}
 +
[[File:Grafy 5barw planar2.svg|250x250px|thumb|right|Grafy 5barw planar2]]
  
 
{{dowod|||
 
{{dowod|||
Linia 340: Linia 331:
 
Dla <math>\left\vert V \right\vert=1</math> teza jest oczywista.  
 
Dla <math>\left\vert V \right\vert=1</math> teza jest oczywista.  
 
Niech więc <math>\left\vert V \right\vert\geq2</math>.  
 
Niech więc <math>\left\vert V \right\vert\geq2</math>.  
Z wniosku [[##cn deg v<<nowiki>=</nowiki>5 dla plan|Uzupelnic cn deg v<<nowiki>=</nowiki>5 dla plan|]] wiemy,  
+
Z [[#wn_14.6|Wniosku 14.6]] wiemy,  
 
że <math>\mathbf{G}</math> ma jakiś wierzchołek <math>v</math> o stopniu niewiększym niż <math>5</math>.  
 
że <math>\mathbf{G}</math> ma jakiś wierzchołek <math>v</math> o stopniu niewiększym niż <math>5</math>.  
 
Na mocy założenia indukcyjnego wiemy,  
 
Na mocy założenia indukcyjnego wiemy,  
Linia 354: Linia 345:
 
odpowiednio o kolorach: <math>1,2,3,4,5</math>.  
 
odpowiednio o kolorach: <math>1,2,3,4,5</math>.  
 
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 [[#Grafy 5barw planar|Grafy 5barw planar]].
 
 
{grafy_5barw_planar}
 
{ '''[Rysunek z pliku:''' <tt>grafy5barwplanar.eps</tt>''']'''}
 
  
 
Niech <math>\mathbf{P}_{i,j}</math> będzie restrykcją grafu <math>\mathbf{G}</math>  
 
Niech <math>\mathbf{P}_{i,j}</math> będzie restrykcją grafu <math>\mathbf{G}</math>  
Linia 372: Linia 360:
 
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>.
 
{grafy_5barw_planar2}
 
{ '''[Rysunek z pliku:''' <tt>grafy5barwplanar2.eps</tt>''']'''}
 
  
 
Z planarności dostajemy więc, że wierzchołki <math>v_2</math> oraz <math>v_4</math>
 
Z planarności dostajemy więc, że wierzchołki <math>v_2</math> oraz <math>v_4</math>
Linia 388: Linia 373:
 
Dowód ten pomijamy.
 
Dowód ten pomijamy.
  
{{twierdzenie|13||
+
{{twierdzenie|14.13|tw 14.13|
 
 
 
Każdy graf planarny jest <math>4</math>-kolorowalny.
 
Każdy graf planarny jest <math>4</math>-kolorowalny.
 
}}
 
}}
Linia 403: Linia 387:
 
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|14||
+
{{twierdzenie|14.14|tw 14.14|
 
 
 
Mapa <math>\mathbf{M}</math> ma <math>2</math>-kolorowalne ściany
 
Mapa <math>\mathbf{M}</math> ma <math>2</math>-kolorowalne ściany
 
wtedy i tylko wtedy, gdy graf <math>\mathbf{M}</math> jest eulerowski.  
 
wtedy i tylko wtedy, gdy graf <math>\mathbf{M}</math> jest eulerowski.  
Linia 410: Linia 393:
  
 
{{dowod|||
 
{{dowod|||
 
 
Załóżmy najpierw, że ściany są pomalowane dwoma kolorami.
 
Załóżmy najpierw, że ściany są pomalowane dwoma kolorami.
 
Wtedy każdy wierzchołek <math>v</math> musi być incydentny z parzystą liczbą ścian,  
 
Wtedy każdy wierzchołek <math>v</math> musi być incydentny z parzystą liczbą ścian,  
Linia 434: Linia 416:
 
}}
 
}}
  
Z Twierdzenia [[##th 4barw planar|Uzupelnic th 4barw planar|]],
+
Z [[#tw_14.13 |Twierdzenia 14.13]],
 
poprzez przejście od mapy <math>\mathbf{M}</math> do grafu geometrycznie dualnego <math>\mathbf{M}^*</math>
 
poprzez przejście od mapy <math>\mathbf{M}</math> do grafu geometrycznie dualnego <math>\mathbf{M}^*</math>
 
dostajemy natychmiast następujący wniosek.
 
dostajemy natychmiast następujący wniosek.
  
{{wniosek|15||
+
{{wniosek|14.15|wn 14.15|
 
 
 
Każda mapa ma  <math>4</math>-kolorowalne ściany.
 
Każda mapa ma  <math>4</math>-kolorowalne ściany.
 
}}
 
}}
Linia 452: Linia 433:
 
<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>
 +
 +
[[File:Grafy liczba stopniowa 1.svg|250x200px|thumb|left|Grafy liczba stopniowa 1]]
 +
 +
[[File:Grafy liczba stopniowa 2.svg|250x150px|thumb|right|Graf <math>\mathbf{G}_1</math> z wierzchołkami w porządku wyznaczonym przez <math>\rho</math>]]
 +
 +
[[File:Grafy liczba stopniowa 3.svg|250x150px|thumb|right|Kolorowanie grafu <math>\mathbf{G}_1</math>]]
 +
 
 +
[[File:Grafy liczba stopniowa animacja.mp4|250x250px|thumb|right|Animacja]]
  
 
{{przyklad|||
 
{{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|Grafy liczba stopniowa 1]].
  
{grafy_liczba_stopniowa_1}
+
Dla permutacji <math>\rho</math> zadanej przez
{Graf <math>\mathbf{G}_1</math>. '''[Rysunek z pliku:''' <tt>grafyliczbastopniowa1.eps</tt>''']'''}
 
  
Dla permutacji <math>\rho</math> zadanej przez
 
  
<center><math>\begin{array} {|c||c|c|c|c|c|}
+
<center>
 +
<math>\begin{array} {|c||c|c|c|c|c|}
 
\hline
 
\hline
 
n&1&2&3&4&5\\
 
n&1&2&3&4&5\\
Linia 472: Linia 461:
 
\hline
 
\hline
 
\end{array}  
 
\end{array}  
</math></center>
+
</math>
 +
</center>
 +
 
  
 
mamy <math>\max_{i=1,\ldots, n}{n_i^{\rho}}=2</math>  
 
mamy <math>\max_{i=1,\ldots, n}{n_i^{\rho}}=2</math>  
 
i wartość ta jest realizowana przez wierzchołki <math>v_3</math> i <math>v_1</math>.  
 
i wartość ta jest realizowana przez wierzchołki <math>v_3</math> i <math>v_1</math>.  
 
Wierzchołki ułożone w porządku <math>v_{\rho\left( 1 \right)},\ldots,v_{\rho\left( 5 \right)}</math>  
 
Wierzchołki ułożone w porządku <math>v_{\rho\left( 1 \right)},\ldots,v_{\rho\left( 5 \right)}</math>  
przedstawione są  na rysunku [[##grafy liczba stopniowa 2|Uzupelnic grafy liczba stopniowa 2|]].
+
przedstawione są  na rysunku [[#Graf z wierzcholkami|Graf G_1 z wierzchołkami...]].
  
 
Przeglądając z kolei wszystkie możliwe permutacje możemy stwierdzić,  
 
Przeglądając z kolei wszystkie możliwe permutacje możemy stwierdzić,  
Linia 483: Linia 474:
 
<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>.
 
{grafy_liczba_stopniowa_2}
 
{Graf <math>\mathbf{G}_1</math> z wierzhołkami w porządku wyznaczonym przez <math>\rho</math>. '''[Rysunek z pliku:''' <tt>grafyliczbastopniowa2.eps</tt>''']'''}
 
  
 
Graf <math>\mathbf{G}_1</math> można teraz pokolorować następującą procedurą.  
 
Graf <math>\mathbf{G}_1</math> można teraz pokolorować następującą procedurą.  
Linia 491: Linia 479:
 
<math>v_{\rho\left( 1 \right)},v_{\rho\left( 2 \right)},\ldots,v_{\rho\left( 5 \right)}</math>  
 
<math>v_{\rho\left( 1 \right)},v_{\rho\left( 2 \right)},\ldots,v_{\rho\left( 5 \right)}</math>  
 
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 [[#Kolorowanie grafu G1|Kolorowanie grafu]].
 
 
{grafy_liczba_stopniowa_3}
 
{Kolorowanie grafu <math>\mathbf{G}_1</math>. '''[Rysunek z pliku:''' <tt>grafyliczbastopniowa3.eps</tt>''']'''}
 
  
 
}}
 
}}
Linia 500: Linia 485:
 
Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.  
 
Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.  
  
{{obserwacje|16||
+
{{obserwacja|14.16|obs 14.16|
 +
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.
 +
</math>
 +
</center>
  
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.
 
</math></center>
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{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>  
 
w porządku realizującym wartość <math>\chi_s\!\left( \mathbf{G} \right)</math>.  
 
w porządku realizującym wartość <math>\chi_s\!\left( \mathbf{G} \right)</math>.  
Linia 521: Linia 509:
 
Przydzielamy go więc wierzchołkowi <math>v_i</math>.  
 
Przydzielamy go więc wierzchołkowi <math>v_i</math>.  
 
Czynność ta jest powtarzana, aż do momentu pokolorowania wszystkich wierzchołków  
 
Czynność ta jest powtarzana, aż do momentu pokolorowania wszystkich wierzchołków  
w <math>{\sf V}\!\left(\mathbf{G}\right)</math>.
+
w <math>\mathsf{ V}\!\left(\mathbf{G}\right)</math>.
 
}}
 
}}

Aktualna wersja na dzień 15:21, 3 paź 2021

Grafy planarne

Graf nieplanarny (a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c)
Grafy k33
Grafy k332

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 w zbiorze .

Graf planarny to graf, który jest prezentowalny jako graf płaski.

Obserwacja 14.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 rysunekGrafy k33.

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 .

Dowód dla jest analogiczny, rozpoczynając od pięcio-elementowego cyklu Hamiltona.

End of proof.gif

Z Obserwacji 14.1 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 oraz , to operacja ta zastępuje graf grafem .
  • Usuwanie wierzchołków stopnia dwa.
    Jeśli ma jedynie dwóch sąsiadów , to operacja ta zastępuje graf grafem .

Grafy homeomorficzne

Przykład

Grafy przedstawione na rysunku Grafy homeomorficzne są ze sobą homeomorficzne, zaś nie jest homeomorficzny ani z ani z .

Następne twierdzenie podaje prostą charakteryzację grafów planarnych. Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.

Twierdzenie 14.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. Grafy sciagalne k33

<flashwrap>file=Grafy sciagalne k33.swf|size=small</flashwrap>

<div.thumbcaption>Graf posiadający podgraf ściągalny do

Graf posiadający cztery ściany:

Twierdzenie 14.3

Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu ściągalnego do lub .

Przykład

W grafie przedstawionym na rysunku Grafy ściagalne k33 ściągnięcie zbiorów wierzchołków otoczonych przerywaną linią prowadzi do grafu zawierającego . A więc, na mocy Twierdzenia 14.3, graf ten nie jest planarny.

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. . Innym słowy ściana to zbiór punktów płaszczyzny, które da się połączyć krzywą nieprzecinającą żadnej krawędzi.

Ściana w grafie z rysunku Graf o czterech ścianach 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 14.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 14.4 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 14.4 pozostawiamy jako ćwiczenie.

Wniosek 14.5

Jeśli jest spójnym grafem planarnym o co najmniej wierzchołkach, to



Wniosek 14.6

Spójny graf planarny o posiada wierzchołek o stopniu nie większym niż .

Graf (w kolorze czerwono-niebieskim) oraz graf do niego dualny geometrycznie (w kolorze żółto-szarym)

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 .

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

Grafy cykl rozC

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 .

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.

Kolorowanie grafu nieoptymalne (a), optymalne (b) oraz niepoprawne (c)

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.

Twierdzenie 14.9

Graf, którego wszystkie wierzchołki mają stopień nie większy niż jest -kolorowalny.

Dowód

Dowód poprowadzimy indukcyjnie 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 14.9 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 14.9, ale podajemy je bez dowodu.

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

Każdy graf planarny jest -kolorowalny.

Grafy 5barw planar

Grafy 5barw planar2

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 14.6 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 Grafy 5barw planar.

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 .

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 14.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.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 14.13, poprzez przejście od mapy do grafu geometrycznie dualnego dostajemy natychmiast następujący wniosek.

Wniosek 14.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


Grafy liczba stopniowa 1
Graf z wierzchołkami w porządku wyznaczonym przez
Kolorowanie grafu

Przykład

Rozważmy graf przedstawiony na rysunku Grafy liczba stopniowa 1.

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 Graf G_1 z wierzchołkami....

Przeglądając z kolei wszystkie możliwe permutacje możemy stwierdzić, że nasza permutacja realizuje minimum , a zatem .

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 Kolorowanie grafu.

Waga wprowadzonej liczby stopniowej wynika z poniższej obserwacji.

Obserwacja 14.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 .

End of proof.gif