Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

From Studia Informatyczne

Grafy III

Ćwiczenie 1

Przedstaw graf nieplanarny, który nie jest homeomorficzny ani ściągalny do \displaystyle \mathcal{K}_{5} oraz \displaystyle \mathcal{K}_{3,3} . Dlaczego nie jest to kontrprzykład dla twierdzeń 14.2 oraz 14.3?

Wskazówka

W Twierdzeniach 14.2 oraz 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.

Rozwiązanie

<flash>file=Cw grafy nieplanarny.swf|width=300|height=150</flash>

1. Graf \displaystyle \mathbf{G}

Graf \displaystyle \mathbf{G} przedstawiony na rysunku 1 nie jest planarny i ponadto nie jest homeomorficzny ani ściągalny do \displaystyle \mathcal{K}_{5} ani \displaystyle \mathcal{K}_{3,3} .

W Twierdzeniach 14.2 oraz 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 \displaystyle \mathbf{G} staje się pełnym grafem dwudzielnym \displaystyle \mathcal{K}_{3,3} .

Ćwiczenie 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?

Wskazówka

Zauważ, że każdy wielościan można tak zrzutować na płąszczyznę \displaystyle \mathbb{R}^2 , by rzut ten reprezentował graf planarny. Skorzystaj z Twierdzenia 14.4.

Rozwiązanie

Przyjmijmy oznaczenia:

  • \displaystyle x - liczba ścian pięciokątnych,
  • \displaystyle y - liczba ścian sześciokątnych.

Suma \displaystyle x+y to liczba wszystkich ścian, więc na mocy twierdzenia 14.4 otrzymujemy


\displaystyle  \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert+\left( x+y \right)=2.      (1)


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


\displaystyle 2\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert=3\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert.


Podstawiając tę zależność w równości (1) przemnożonej przez \displaystyle 2 , dostajemy:


\displaystyle  2\left( x+y \right)-\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert=4.      (2)


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


\displaystyle 3\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert=5x+6y.


Podstawiając tę zależność w równości (2) przemnożonej przez \displaystyle 3 , dostajemy:


\displaystyle 6\left( x+y \right)-5x-6y=12.


Liczba ścian pięciokątnych wynosi więc \displaystyle x=12 .

Ćwiczenie 3

Pokaż, że dla spójnego, prostego grafu planarnego \displaystyle \mathbf{G}=\left( V,E \right) o co najmniej trzech wierzchołkach zachodzi


\displaystyle \left\vert E \right\vert\leq 3\left\vert V \right\vert-6.


Wskazówka

Wykorzystaj Twierdzenie 14.4.

Rozwiązanie

Rozważmy dowolną płaską reprezentacje grafu \displaystyle \mathbf{G} . Ponieważ \displaystyle \mathbf{G} 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 \displaystyle \left( e,w \right) takich, że krawędź \displaystyle e ogranicza ścianę \displaystyle w , otrzymujemy nierówność


\displaystyle 3f\leq 2\left\vert E \right\vert,


gdzie \displaystyle f to liczba ścian w rozważanej płaskiej prezentacji. Po podstawieniu tej nierówności do wzoru z Twierdzenia 14.4 otrzymujemy:


\displaystyle 2 =\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert+f \leq\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\frac{1}{3}\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert,


co po prostym przekształceniu daje:


\displaystyle \left\vert E \right\vert\leq 3\left\vert V \right\vert-6.


Ćwiczenie 4

Pokaż, że spójny graf planarny \displaystyle \mathbf{G} o co najmniej jednym wierzchołku posiada wierzchołek o stopniu nie większym niż \displaystyle 5 .

Wskazówka

Skorzystaj z Twierdzenia 14.4 oraz z Ćwiczenia 3.

Rozwiązanie

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 \displaystyle \mathbf{G} jest spójnym, płaskim grafem o co najmniej trzech wierzchołkach. Załóżmy, że każdy wierzchołek \displaystyle \mathbf{G} ma stopień co najmniej sześć. Wtedy zależność między stopniami wierzchołków, a liczbą krawędzi daje:


\displaystyle 6\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq 2\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert.


Korzystając z Ćwiczenia 3 otrzymujemy:


\displaystyle 3\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq 3\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-6,


co jest sprzecznością.

Ćwiczenie 5

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

Wskazówka

Zauważ, że w ciągach odpowiadających sąsiednim wierzchołkom liczby jedynek różnią się parzystością.

Rozwiązanie

Podzielmy wierzchołki kostki \displaystyle \mathcal{Q}_{k} na dwa zbiory:

  • \displaystyle V_1\subseteq {\sf V}\!\left(\mathcal{Q}_{k}\right) to zbiór wierzchołków o nieparzystej liczbie jedynek,
  • \displaystyle V_2\subseteq {\sf V}\!\left(\mathcal{Q}_{k}\right) to zbiór wierzchołków o parzystej liczbie jedynek,

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

Ćwiczenie 6

Nie korzystając z Twierdzenia 14.13 o czterech barwach pokaż, że graf planarny bez trójkątów jest czterokolorowalny.

Wskazówka

Pokaż, że w grafie planarnym bez trójkątów, istnieje wierzchołek stopnia co najwyżej trzy.

Rozwiązanie

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, \displaystyle graf{G} 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


\displaystyle 4f\leq 2\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert,


gdzie \displaystyle f oznacza liczbę ścian w grafie \displaystyle \mathbf{G} . Korzystając z Twierdzenia 14.4 otrzymujemy, że


\displaystyle 4 =2\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-2\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert+2f \leq 2\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert,


skąd


\displaystyle \left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert\leq 2\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-4.


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


\displaystyle 4\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq 2 \left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert.


Prowadzi to natychmiast do sprzeczności postaci


\displaystyle 2\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq  \left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert\leq 2\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert-4.


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