Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

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

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 {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert -\left\vert {\mathsf {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 {\mathsf {E}}\!\left(\mathbf {G} \right)\right\vert =3\left\vert {\mathsf {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 {\mathsf {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 {\mathsf {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 {\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 ,$

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 {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert \leq 2\left\vert {\mathsf {E}}\!\left(\mathbf {G} \right)\right\vert .$

Korzystając z Ćwiczenia 3 otrzymujemy:

$\displaystyle 3\left\vert {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert \leq 3\left\vert {\mathsf {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 {\mathsf {V}}\!\left({\mathcal {Q}}_{k}\right)$ to zbiór wierzchołków o nieparzystej liczbie jedynek,
• $\displaystyle V_{2}\subseteq {\mathsf {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},{\mathsf {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 {\mathsf {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 {\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 ,$

skąd

$\displaystyle \left\vert {\mathsf {E}}\!\left(\mathbf {G} \right)\right\vert \leq 2\left\vert {\mathsf {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 {\mathsf {V}}\!\left(\mathbf {G} \right)\right\vert \leq 2\left\vert {\mathsf {E}}\!\left(\mathbf {G} \right)\right\vert .$

Prowadzi to natychmiast do sprzeczności postaci

$\displaystyle 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.$

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.