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 $\displaystyle {\mathcal {K}}_{5}$ oraz $\displaystyle {\mathcal {K}}_{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 $\displaystyle \mathbf {G}$ przedstawiony na rysunku Uzupelnic cw grafy nieplanarny| nie jest planarny i ponadto nie jest homeomorficzny ani ściągalny do $\displaystyle {\mathcal {K}}_{5}$ ani $\displaystyle {\mathcal {K}}_{3,3}$ .

[!ht]

{cw_grafy_nieplanarny} {Graf $\displaystyle \mathbf {G}$ . [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 $\displaystyle \mathbf {G}$ staje się pełnym grafem dwudzielnym $\displaystyle {\mathcal {K}}_{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ę $\displaystyle \mathbb {R} ^{2}$ , by rzut ten reprezentował graf planarny. Skorzystaj z Twierdzenia [th][th ilosc krawedzi].

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

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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ć (nieznana funkcja „\sf”): {\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 $\displaystyle 2$ , dostajemy:

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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 $\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:

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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 $\displaystyle 3$ , dostajemy:

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

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

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

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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:

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

Ćwiczenie ex deg v<=5 dla plan

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 [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 $\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:

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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ć (nieznana funkcja „\sf”): {\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ą $\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:

• Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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ć (nieznana funkcja „\sf”): {\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 $\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 Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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, $\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

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\displaystyle \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 [th][th ilosc krawedzi] otrzymujemy, że

Parser nie mógł rozpoznać (nieznana funkcja „\sf”): {\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ć (nieznana funkcja „\sf”): {\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ć (nieznana funkcja „\sf”): {\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ć (nieznana funkcja „\sf”): {\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 $\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.