Deltoid

Domki i studnie

Zagadka. Bracia Jacek, Wacek i Placek mieszkają w trzech różnych domkach, w pobliżu których znajdują się trzy studnie: jedna z $\text{[math]}$ druga z $\text{[math]}$ trzecia z sokiem porzeczkowym. Każdy z braci chciałby poprowadzić ze swojego domu trzy chodniki, po jednym do każdej ze studni. Czy bracia mogą poprowadzić swoich 9 chodników tak, aby żadne dwa z nich się nie przecinały (Rys. 1)?

Zapewne wielu Czytelników jeszcze w dzieciństwie przekonało się, metodą prób i błędów, że odpowiedź brzmi „nie”. Aby ją udowodnić, wprowadźmy kilka pojęć z teorii grafów.

Grafy dwudzielne.

Graf to, mówiąc intuicyjnie, punkty (zwane wierzchołkami) połączone liniami (niekoniecznie prostymi, zwanymi krawędziami). Rozważać będziemy tylko grafy spójne, czyli „w jednym kawałku”, i proste, czyli takie, w których każda krawędź ma dwa różne końce i żadnych dwóch wierzchołków nie łączy bezpośrednio więcej niż jedna krawędź (Rys. 2).

Rys. 3 Różne sposoby narysowania grafu $\text{[math]}$

$\text{[math]}$ oznacza graf pełny o $\text{[math]}$ wierzchołkach, czyli graf o $\text{[math]}$ wierzchołkach, z których każde dwa są połączone krawędzią (Rys. 3 i Rys. 4).

Graf pełny dwudzielny $\text{[math]}$ to taki graf, którego $\text{[math]}$ wierzchołków można podzielić na dwie grupy, po $\text{[math]}$ i $\text{[math]}$ a krawędzie łączą wszystkie wierzchołki z jednej grupy ze wszystkimi z drugiej, przy czym innych krawędzi nie ma. W przypadku trzech domków i trzech studni występuje graf $\text{[math]}$

Grafy planarne.

Graf nazywamy planarnym, jeśli da się go narysować na płaszczyźnie tak, aby żadne dwie krawędzie się nie przecinały. Na przykład graf $\text{[math]}$ jest planarny (Rys. 3). Nie wszystkie grafy są planarne.

W zagadce o domkach i studniach należy rozstrzygnąć, czy graf $\text{[math]}$ jest planarny.

Wzór Eulera i przydatna nierówność.

Dla grafów planarnych zachodzi wzór Eulera:

display-math

gdzie $\text{[math]}$ to liczba wierzchołków grafu, $\text{[math]}$ – liczba krawędzi, a $\text{[math]}$ – liczba ścian, czyli obszarów, na jakie graf dzieli płaszczyznę (wliczamy też „zewnętrze” grafu).

Wykażemy teraz, że w planarnym grafie dwudzielnym zachodzi nierówność

display-math

(*)

Policzmy krawędzie takiego grafu. Każda ściana ma na przemian wierzchołki z każdej z dwóch grup, zatem jest parzystokątna, więc co najmniej czworokątna. Ma wobec tego co najmniej 4 krawędzie. W grafie jest więc co najmniej $\text{[math]}$ krawędzi, ale – uwaga! – policzonych dwukrotnie (każdą krawędź liczymy przy każdej z dwóch ścian, które rozdziela). Stąd $\text{[math]}$

Rozwiązanie zagadki. Pokażemy, że graf $\text{[math]}$ nie jest planarny, czyli że bracia nie są w stanie poprowadzić nieprzecinających się chodników. Przypuśćmy przeciwnie. Wtedy ze wzoru Eulera mamy $\text{[math]}$ przy czym $\text{[math]}$ $\text{[math]}$ Stąd $\text{[math]}$ Jednocześnie na mocy (*) zachodzi $\text{[math]}$ czyli $\text{[math]}$ sprzeczność.

Zadania domowe

Zadanie 1. Udowodnij wzór Eulera.

Zadanie 2. Wykaż, że wierzchołki i krawędzie dowolnego wielościanu wypukłego tworzą graf planarny prosty.

Zadanie 3. Wykaż, że dla każdego wielościanu wypukłego zachodzi $\text{[math]}$ oraz $\text{[math]}$

Zadanie 4. Wykaż, że graf $\text{[math]}$ nie jest planarny (Rys. 4).

Zadanie 5. Czy istnieje takie $\text{[math]}$ że graf $\text{[math]}$ jest planarny?

Ważna uwaga na koniec. Z rozwiązania zagadki o domkach i studniach oraz z zadania 4 można wywnioskować, że jeśli graf zawiera „fragment typu” $\text{[math]}$ lub $\text{[math]}$ to nie może być planarny (ponieważ już ten fragment nie daje się narysować bez przecinających się krawędzi, a co dopiero cały graf).

Twierdzenie Kuratowskiego głosi, że zachodzi także fakt odwrotny, czyli że graf jest nieplanarny wtedy i tylko wtedy, gdy zawiera „fragment typu” $\text{[math]}$ lub $\text{[math]}$ Twierdzenie to oznacza, że te dwa niezwykle proste grafy nieplanarne ( $\text{[math]}$ i $\text{[math]}$ ) wystarczają, by rozstrzygać o planarności lub nieplanarności wszystkich innych grafów, a także że – w pewnym sensie – nie ma żadnego „naprawdę zupełnie innego” od nich grafu nieplanarnego.