Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

Grafy III

Ćwiczenie 1

Przedstaw graf nieplanarny, który nie jest homeomorficzny ani ściągalny do ${{𝒦}}_5$ oraz ${{𝒦}}_{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>

<div.thumbcaption>1. Graf $\mathbf{𝐆}$

Graf $\mathbf{𝐆}$ przedstawiony na rysunku 1 nie jest planarny i ponadto nie jest homeomorficzny ani ściągalny do ${{𝒦}}_5$ ani ${{𝒦}}_{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 $\mathbf{𝐆}$ staje się pełnym grafem dwudzielnym ${{𝒦}}_{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ę ${\mathbb{ℝ}}^2$ , by rzut ten reprezentował graf planarny. Skorzystaj z Twierdzenia 14.4.

Rozwiązanie

Przyjmijmy oznaczenia:

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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $2$ , dostajemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $x$ ścian ma pięć wierzchołków, a $y$ sześć. Licząc więc pary $(v,f)$ , gdzie wierzchołek $v$ leży na ścianie $f$ , dostajemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $3$ , dostajemy:

$6(x+y)-5x-6y=12.$

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

Ćwiczenie 3

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

$\left|E\right|\le 3\left|V\right|-6.$

Wskazówka

Wykorzystaj Twierdzenie 14.4.

Rozwiązanie

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

$3f\le 2\left|E\right|,$

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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:

$\left|E\right|\le 3\left|V\right|-6.$

Ćwiczenie 4

Pokaż, że spójny graf planarny $\mathbf{𝐆}$ o co najmniej jednym wierzchołku posiada wierzchołek o stopniu nie większym niż $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 $\mathbf{𝐆}$ jest spójnym, płaskim grafem o co najmniej trzech wierzchołkach. Załóżmy, że każdy wierzchołek $\mathbf{𝐆}$ ma stopień co najmniej sześć. Wtedy zależność między stopniami wierzchołków, a liczbą krawędzi daje:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ą $k$ -wymiarowej kostki ${{𝒬}}_k$ , czyli grafu, którego wierzchołki to ciągi $(a_1,a_2,\dots ,a_k)$ , gdzie $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 ${{𝒬}}_k$ na dwa zbiory:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle V_1\subseteq {\sf V}\!\left(\mathcal{Q}_{k}\right) } to zbiór wierzchołków o nieparzystej liczbie jedynek,
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $1$ , w szczególności różni się parzystością. A zatem miedzy wierzchołkami z $V_i$ nie ma krawędzi, czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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, $grafG$ 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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 4f\leq 2\left\vert {\sf E}\!\left(\mathbf{G}\right) \right\vert, }

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $\mathbf{𝐆}$ bez trójkątów poprowadzimy teraz indukcyjnie ze względu na liczbę wierzchołków $n$ tego grafu. Dla grafów o $n=1$ jest to oczywiste. Załóżmy, że $n\ge 2$ . Jak już wiemy, w planarnym grafie bez trójkątów istnieje wierzchołek, powiedzmy $v$ , o stopniu co najwyżej trzy. Graf $\mathbf{𝐆}-\left\{v\right\}$ ma $n-1$ wierzchołków więc, na mocy założenia indukcyjnego, można go pokolorować czterema kolorami. Wierzchołek $v$ miał co najwyżej trzech sąsiadów, więc musi istnieć kolor $c$ nie wykorzystany przez sąsiadów $v$ . Wierzchołek $v$ kolorujemy właśnie na kolor $c$ . Uzyskaliśmy w konsekwencji kolorowanie grafu $\mathbf{𝐆}$ za pomocą czterech barw, co kończy dowód.