Tekst źródłowy strony Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

==Grafy III==

{{cwiczenie|1|cw 1|
Przedstaw graf nieplanarny, który nie jest homeomorficzny ani ściągalny 
do  <math>\mathcal{K}_{5}</math>  oraz  <math>\mathcal{K}_{3,3}</math> . 
Dlaczego nie jest to kontrprzykład dla twierdzeń [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.2|14.2]] oraz [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.3|14.3]]?

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
W Twierdzeniach [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.2|14.2]] oraz [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.3|14.3]] jest mowa, że aby graf był planarny, to dowolny podgraf musi spełniać pewne warunki.
Tak więc przed szukaniem zabronionych struktur możemy usunąć z grafu dowolną liczbę wierzchołków oraz krawędzi.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

[[File:Cw grafy nieplanarny.svg|300x150px|thumb|right" id="cw_grafy_nieplanarny|1. Graf  <math>\mathbf{G}</math>]]

Graf  <math>\mathbf{G}</math>  przedstawiony na [[#cw grafy nieplanarny|rysunku 1]] nie jest planarny 
i ponadto nie jest homeomorficzny ani ściągalny do  <math>\mathcal{K}_{5}</math>  ani  <math>\mathcal{K}_{3,3}</math> .

W Twierdzeniach [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.2|14.2]] oraz [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.3|14.3]] jest mowa, że aby graf był planarny, to dowolny podgraf musi spełniać określone warunki. 
Tak więc przed szukaniem zabronionych struktur możemy więc usunąć z grafu dowolną liczbę wierzchołków oraz krawędzi. Faktycznie, po usunięciu czerwonej krawędzi graf  <math>\mathbf{G}</math> staje się pełnym grafem dwudzielnym  <math>\mathcal{K}_{3,3}</math> .
</div></div>

{{cwiczenie|2|cw 2|
W pewnym wielościanie wszystkie ściany są  pięciokątami i sześciokątami. 
Ile jest ścian pięciokątnych, 
jeżeli w każdym wierzchołku spotykają się dokładnie trzy ściany?

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Zauważ, że każdy wielościan można tak zrzutować na płąszczyznę  <math>\mathbb{R}^2</math> ,
by rzut ten reprezentował graf planarny. 
Skorzystaj z Twierdzenia [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.4|14.4]].
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Przyjmijmy oznaczenia:
*  <math>x</math> - liczba ścian pięciokątnych,
*  <math>y</math> - liczba ścian sześciokątnych.

Suma  <math>x+y</math>  to liczba wszystkich ścian, 
więc na mocy twierdzenia [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.4|14.4]] otrzymujemy


{{wzor|1|1|
<math>
\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert+\left( x+y \right)=2</math>}}


Każdy wierzchołek jest incydentny z trzema krawędziami, 
zaś każda krawędź jest incydentna z dwoma wierzchołkami, skąd


<center><math>2\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert=3\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert</math></center>


Podstawiając tę zależność w równości ([[#1|1]]) przemnożonej przez  <math>2</math> , dostajemy:


{{wzor|2|2|
<math>
2\left( x+y \right)-\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert=4</math>}}


Każdy wierzchołek leży na trzech ścianach. 
Z drugiej strony  <math>x</math>  ścian ma pięć wierzchołków, a  <math>y</math>  sześć.
Licząc więc  pary  <math>\left( v,f \right)</math> , gdzie wierzchołek  <math>v</math>  
leży na ścianie  <math>f</math> , dostajemy:


<center><math>3\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert=5x+6y</math></center>


Podstawiając tę zależność w równości ([[#2|2]]) przemnożonej przez  <math>3</math> , dostajemy:


<center><math>6\left( x+y \right)-5x-6y=12</math></center>


Liczba ścian pięciokątnych wynosi więc  <math>x=12</math> .
</div></div>

{{cwiczenie|3|cw 3|
Pokaż, że dla spójnego, prostego grafu planarnego  <math>\mathbf{G}=\left( V,E \right)</math>  o co najmniej trzech wierzchołkach zachodzi


<center><math>\left\vert E \right\vert\leq 3\left\vert V \right\vert-6</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Wykorzystaj Twierdzenie [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.4|14.4]].
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Rozważmy dowolną płaską reprezentacje grafu  <math>\mathbf{G}</math> . 
Ponieważ  <math>\mathbf{G}</math>  jest grafem prostym, to
dowolna ściana w tej reprezentacji jest ograniczona przez co najmniej trzy krawędzie. 
Z drugiej strony każda krawędź graniczy z co najwyżej dwiema ścianami. 
Po przeliczeniu par  <math>\left( e,w \right)</math>  takich, że krawędź  <math>e</math>  ogranicza ścianę  <math>w</math> , 
otrzymujemy nierówność


<center><math>3f\leq 2\left\vert E \right\vert</math>,</center>


gdzie  <math>f</math>  to liczba ścian w rozważanej płaskiej prezentacji.
Po podstawieniu tej nierówności do wzoru z Twierdzenia [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.4|14.4]] otrzymujemy:


<center><math>2
=\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert+f
\leq\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-\frac{1}{3}\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert</math>,</center>


co po prostym przekształceniu daje:


<center><math>\left\vert E \right\vert\leq 3\left\vert V \right\vert-6</math></center>


</div></div>

{{cwiczenie|4|cw 4|
Pokaż, że spójny graf planarny  <math>\mathbf{G}</math>  
o co najmniej jednym wierzchołku posiada wierzchołek 
o stopniu nie większym niż  <math>5</math> .

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Skorzystaj z Twierdzenia [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.4|14.4]] oraz z Ćwiczenia [[#cw_3|3]].
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Oczywiście taki wierzchołek musi istnieć w grafie z jednym bądź dwoma wierzchołkami.
Bez straty ogólności możemy przyjąć, 
że  <math>\mathbf{G}</math>  jest spójnym, płaskim grafem o co najmniej trzech wierzchołkach. 
Załóżmy, że każdy wierzchołek  <math>\mathbf{G}</math>  ma stopień co najmniej sześć. 
Wtedy zależność między stopniami wierzchołków, a liczbą krawędzi daje:


<center><math>6\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert\leq 2\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert</math></center>


Korzystając z Ćwiczenia [[#cw_3|3]] otrzymujemy:


<center><math>3\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert\leq 3\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-6</math>,</center>


co jest sprzecznością.
</div></div>

{{cwiczenie|5|cw 5|
Znajdź liczbę chromatyczną  <math>{k}</math> -wymiarowej kostki  <math>\mathcal{Q}_{k}</math> , czyli 
grafu, którego wierzchołki to ciągi  <math>\left( a_1,a_2,\ldots,a_k \right)</math> , gdzie  <math>a_i=0,1</math> , 
a krawędzie łączą te ciągi, które różnią się tylko na jednej pozycji. 

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Zauważ, że w ciągach odpowiadających sąsiednim wierzchołkom 
liczby jedynek różnią się parzystością.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Podzielmy wierzchołki kostki  <math>\mathcal{Q}_{k}</math>  na dwa zbiory: 
*  <math>V_1\subseteq \mathsf{ V}\!\left(\mathcal{Q}_{k}\right)</math>  to zbiór wierzchołków o nieparzystej liczbie jedynek,
*  <math>V_2\subseteq \mathsf{ V}\!\left(\mathcal{Q}_{k}\right)</math>  to zbiór wierzchołków o parzystej liczbie jedynek,

W sąsiednich  wierzchołkach liczba jedynek różni się o  <math>1</math> , 
w szczególności różni się parzystością.
A zatem miedzy wierzchołkami z  <math>V_i</math>  nie ma krawędzi, 
czyli  <math>\mathcal{Q}_{k}=\left( V_1\cup V_2, \mathsf{ E}\!\left(\mathcal{Q}_{k}\right) \right)</math>  
jest grafem dwudzielnym, czyli dwukolorowalnym.
</div></div>

{{cwiczenie|6|cw 6|
Nie korzystając z Twierdzenia [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.13|14.13]] o czterech barwach pokaż, że graf planarny bez trójkątów jest czterokolorowalny.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">   
Pokaż, że w grafie  planarnym bez trójkątów, 
istnieje wierzchołek stopnia co najwyżej trzy.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Pokażemy najpierw, że w grafie  planarnym bez trójkątów, 
istnieje wierzchołek stopnia co najwyżej trzy.
Niech więc, dla dowodu niewprost, 
<math>graf{G}</math>  będzie płaską prezentacją grafu bez trójkątów, 
w którym każdy wierzchołek ma stopień conajmniej cztery. 
Z faktu, że każda krawędź ogranicza co najmniej dwie ściany, 
a każda ściana jest ograniczona przez co najmniej cztery krawędzie mamy


<center><math>4f\leq 2\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert</math>,</center>


gdzie  <math>f</math>  oznacza liczbę ścian w grafie  <math>\mathbf{G}</math> . 
Korzystając z Twierdzenia [[Matematyka dyskretna 1/Wykład 14: Grafy III#tw_14.4|14.4]] otrzymujemy, że


<center><math>4
=2\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-2\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert+2f
\leq 2\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert</math>,</center>


skąd


<center><math>\left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert\leq 2\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-4</math></center>


Z drugiej strony dowolny wierzchołek jest incydentny z co najmniej czterema krawędziami, 
zaś każda krawędź jest incydentna z dwoma wierzchołkami, więc


<center><math>4\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert\leq 2 \left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert</math></center>


Prowadzi to natychmiast do sprzeczności postaci


<center><math>2\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert\leq  \left\vert \mathsf{ E}\!\left(\mathbf{G}\right) \right\vert\leq 2\left\vert \mathsf{ V}\!\left(\mathbf{G}\right) \right\vert-4</math></center>


Dowód trójkolorowalności planarnego grafu  <math>\mathbf{G}</math>  bez trójkątów 
poprowadzimy teraz indukcyjnie ze względu na  liczbę wierzchołków  <math>n</math>  tego grafu. 
Dla grafów o  <math>n=1</math>  jest to oczywiste.
Załóżmy, że  <math>n\geq 2</math> . 
Jak już wiemy, w planarnym grafie bez trójkątów 
istnieje wierzchołek, powiedzmy  <math>v</math> , o stopniu co najwyżej trzy. 
Graf  <math>\mathbf{G}-\left\lbrace v \right\rbrace</math>  ma  <math>n-1</math>  wierzchołków  
więc, na mocy założenia indukcyjnego, można go pokolorować czterema kolorami. 
Wierzchołek  <math>v</math>  miał co najwyżej trzech sąsiadów, 
więc musi istnieć kolor  <math>c</math>  nie wykorzystany przez sąsiadów  <math>v</math> . 
Wierzchołek  <math>v</math>  kolorujemy właśnie na kolor  <math>c</math> . 
Uzyskaliśmy w konsekwencji kolorowanie grafu  <math>\mathbf{G}</math>  za pomocą czterech barw, 
co kończy dowód.
</div></div>