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

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

$\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|+(x+y)=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

$2\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|=3\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|$

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

$2(x+y)-\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|=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:

$3\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|=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:

$2=\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|+f\le \left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-\frac{1}{3}\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|$,

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:

$6\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|\le 2\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|$

Korzystając z Ćwiczenia 3 otrzymujemy:

$3\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|\le 3\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-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:

• $V_1\subseteq \mathsf{V}\left({{𝒬}}_k\right)$ to zbiór wierzchołków o nieparzystej liczbie jedynek,
• $V_2\subseteq \mathsf{V}\left({{𝒬}}_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 ${{𝒬}}_k=(V_1\cup V_2,\mathsf{E}\left({{𝒬}}_k\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

$4f\le 2\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|$,

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

$4=2\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-2\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|+2f\le 2\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|$,

skąd

$\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|\le 2\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-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

$4\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|\le 2\left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|$

Prowadzi to natychmiast do sprzeczności postaci

$2\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|\le \left|\mathsf{E}\left(\mathbf{𝐆}\right)\right|\le 2\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|-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.