Matematyka dyskretna 1/Ćwiczenia 14: Grafy III

Grafy III

Ćwiczenie ex grafy Kuratowski kontr

Przedstaw graf nieplanarny, który nie jest homeomorficzny ani ściągalny do ${{𝒦}}_5$ oraz ${{𝒦}}_{3,3}$ . Dlaczego nie jest to kontrprzykład dla twierdzeń [th][th Kuratowski] oraz [th][th sciagalny k5k33]?

Wskazówka

W Twierdzeniach [th][th Kuratowski] oraz [th][th sciagalny k5k33] 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

Graf $\mathbf{𝐆}$ przedstawiony na rysunku Uzupelnic cw grafy nieplanarny| nie jest planarny i ponadto nie jest homeomorficzny ani ściągalny do ${{𝒦}}_5$ ani ${{𝒦}}_{3,3}$ .

[!ht]

{cw_grafy_nieplanarny} {Graf $\mathbf{𝐆}$ . [Rysunek z pliku: cwgrafynieplanarny.eps]}

W Twierdzeniach [th][th Kuratowski] oraz [th][th sciagalny k5k33] 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 ex grafy pilka

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 [th][th ilosc krawedzi].

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 [th][th ilosc krawedzi] 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. }

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 (Uzupelnic eq grafy pilka Euler|) 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. }

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 (Uzupelnic eq grafy pilka Euler 2|) przemnożonej przez $3$ , dostajemy:

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

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

Ćwiczenie ex m<=3n-6 dla plan

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 [th][th ilosc krawedzi].

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 [th][th ilosc krawedzi] 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 ex deg v<=5 dla plan

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 [th][th ilosc krawedzi] oraz z Ćwiczenia [[##ex m<=3n-6 dla plan|Uzupelnic ex m<=3n-6 dla plan|]].

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 [[##ex m<=3n-6 dla plan|Uzupelnic ex m<=3n-6 dla plan|]] 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 ex grafy

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 ex grafy

Nie korzystając z Twierdzenia [th][th 4barw planar] 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 [th][th ilosc krawedzi] 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.