Graf płaski to para: ¯G=(¯V,¯E), gdzie
Graf planarny to graf, który jest prezentowalny jako graf płaski.
Obserwacja 14.1
Grafy K5 i K3,3 nie są planarne.
Dowód
Graf K3,3 ma sześcio-elementowy cykl Hamiltona H. Musi on być narysowany w dowolnej płaskiej prezentacji. Przykładowe umiejscowienie tego cyklu prezentuje rysunek Grafy k33.
Spośród krawędzi v1v4 i v2v5 jedna musi leżeć wewnątrz cyklu a druga musi leżeć na zewnątrz. W konsekwencji nie da się narysować krawędzi v3v0 nie przecinając krawędzi v1v4 lub v2v5.
Dowód dla K5 jest analogiczny, rozpoczynając od pięcio-elementowego cyklu Hamiltona.
Z Obserwacji 14.1 natychmiast wynika, że żaden graf zawierający K5 lub K3,3 nie jest planarny. Ale również graf powstały np. z K5 poprzez umieszczenie na jednej krawędzi dodatkowego wierzchołka nie jest planarny mimo, że nie zawiera podgrafu K5 ani K3,3. Dla scharakteryzowania grafów planarnych potrzebne nam będzie następujące pojęcie homeomorficzności grafów.
Graf G1 jest homeomorficzny z grafem G2, jeśli jeden otrzymamy z drugiego poprzez wykonanie skończenie wielu poniższych operacji:
Przykład
Grafy G,G′ przedstawione na rysunku Grafy homeomorficzne są ze sobą homeomorficzne, zaś G″ nie jest homeomorficzny ani z \mathbf{G} ani z \mathbf{G}' .
Następne twierdzenie podaje prostą charakteryzację grafów planarnych. Niestety dowód tego twierdzenia nie jest prosty i go pominiemy.
Twierdzenie 14.2 [Kuratowski 1930]
Graf jest planarny wtedy i tylko wtedy, gdy żaden jego podgraf nie jest homeomorficzny z \mathcal{K}_{5} ani z \mathcal{K}_{3,3} .
Kolejne charakterystyka grafów planarnych odwołuje się do znanego nam już pojęcia sciągalności, lub grafu ilorazowego. Przypomnijmy, że
\mathbf{G}/\theta=( V/\theta,\lbrace \lbrace v/\theta,w/\theta \rbrace:\lbrace v,w \rbrace\in E \rbrace ),
Dowód charakteryzacji grafów planarnych w terminach ściągalności również pomijamy. Grafy sciagalne k33
Twierdzenie 14.3
Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu ściągalnego do \mathcal{K}_{5} lub \mathcal{K}_{3,3} .
Przykład
W grafie przedstawionym na rysunku Grafy ściagalne k33 ściągnięcie zbiorów wierzchołków otoczonych przerywaną linią prowadzi do grafu zawierającego \mathcal{K}_{3,3} . A więc, na mocy Twierdzenia 14.3, graf ten nie jest planarny.
W grafach płaskich poza wierzchołkami oraz krawędziami można rozważać również ściany, czyli obszary płaszczyzny otoczone krawędziami.
Ściana w grafie płaskim \mathbf{G} to spójny obszar płaszczyzny po usunięciu linii reprezentujących krawędzie, tzn. R^2-\bigcup{\sf E}\!(\mathbf{G}) . Innym słowy ściana to zbiór punktów płaszczyzny, które da się połączyć krzywą nieprzecinającą żadnej krawędzi.
Ściana f_0 w grafie z rysunku Graf o czterech ścianach jest ścianą nieograniczoną, która nazywana jest też ścianą nieskończoną. Nie tylko ten graf, ale wszystkie grafy płaskie mają dokładnie jedną ścianę nieskończoną. Zauważmy, że las jest grafem planarnym, ale w żadnej reprezentacji płaskiej nie posiada ścian ograniczonych. Tak więc posiada w ogóle tylko jedną ścianę. Tym samym, następne twierdzenie jest uogólnieniem związku \vert E \vert=\vert V \vert-k między liczbą wierzchołków, krawędzi i drzew (tzn. spójnych składowych) w lesie.
Twierdzenie 14.4 [Euler 1750]
W grafie płaskim \mathbf{G}=( V,E ) o f ścianach i k\geq 1 składowych spójnych zachodzi
\vert V \vert-\vert E \vert+f=k+1.
Dowód
Dowód poprowadzimy indukcją ze względu na liczbę krawędzi. Jeżeli graf \mathbf{G} jest pusty to \vert E \vert=0,k=\vert V \vert,\ f=1 , które to wartości spełniają podaną równość. Załóżmy, że \vert E \vert>1 . Wybierzmy dowolną krawędź uv\in E . Jeżeli uv nie leży na żadnym cyklu grafu \mathbf{G} , to usunięcie uv zwiększy o 1 liczbę składowych ale nie zmieni liczby ścian. Tak więc, na mocy założenia indukcyjnego, \vert V \vert-(\vert E \vert-1)+f=(k+1)+1 , co daje żądaną równość. Załóżmy więc, że uv leży na jakimś cyklu C . Tym samym uv jest granicą pomiędzy dwoma różnymi ścianami, jako że dowolna krzywa przechodząca z jednej strony na drugą stronę granicy wyznaczonej przez krawędź uv musi przecinać jakąś krawędź z cyklu C . Tak więc usunięcie krawędzi uv zmniejszy liczbę ścian o jeden. Ale teraz usunięcie krawędzi uv nie zmienia liczby składowych. Założenie indukcyjne daje nam więc \vert V \vert-(\vert E \vert-1)+(f-1)=k+1 , czyli żądaną równość dla grafu \mathbf{G} .
Uwaga
Ważną konsekwencją Twierdzenia 14.4 jest to, że liczba ścian zależy jedynie od liczby wierzchołków, krawędzi, oraz spójnych składowych. Tak więc w każdej reprezentacji płaskiej musi być taka sama.
Uzasadnienie dwu kolejnych wniosków z Twierdzenia 14.4 pozostawiamy jako ćwiczenie.
Wniosek 14.5
Jeśli \mathbf{G}=( V,E ) jest spójnym grafem planarnym o co najmniej 3 wierzchołkach, to
\vert E \vert\leq 3\vert V \vert-6.
Wniosek 14.6
Spójny graf planarny o \vert V \vert\geq1 posiada wierzchołek o stopniu nie większym niż 5 .
Graf (w kolorze czerwono-niebieskim) oraz graf do niego dualny geometrycznie (w kolorze żółto-szarym)
Graf dualny geometrycznie do grafu płaskiego \mathbf{G}=( V,E ) to graf płaski \mathbf{G}^*=( V^*,E^* ) skonstruowany w następujący sposób:
Twierdzenie 14.7
Jeśli \mathbf{G} jest spójnym grafem płaskim, to \mathbf{G}^{**} jest izomorficzny z \mathbf{G} .
Dowód
Każda ściana grafu \mathbf{G}^{*} reprezentowana jest jednym wierzchołkiem \mathbf{G}^{**} . Z drugiej strony, w każdej ścianie grafu \mathbf{G}^{*} znajduje się dokładnie jeden wierzchołek grafu \mathbf{G} . Ponadto, jeśli wierzchołki v_1,v_2 grafu \mathbf{G} są sąsiednie, to ściany f_1^*,f_2^* grafu \mathbf{G}^{*} zawierające odpowiednio v_1 i v_2 graniczą ze sobą. To kolei oznacza, że wierzchołki v_1^{**},v_2^{**} grafu \mathbf{G}^{**} odpowiadające ścianom f_1^* oraz f_2^* są sąsiednie. Oczywiście, przy przejściu z \mathbf{G} do \mathbf{G}^{*} i potem do \mathbf{G}^{**} wierzchołki v_1 i v_2 przechodzą w v_1^{**},v_2^{**} . Analogicznie jeżeli v_1^{**} jest połączony krawędzią z v_2^{**} w \mathbf{G}^{**} , to i również v_1 z v_2 w \mathbf{G} .
Twierdzenie 14.8
Niech \mathbf{G}^* będzie grafem geometrycznie dualnym do grafu płaskiego \mathbf{G} . Wtedy podzbiór C krawędzi grafu \mathbf{G} jest cyklem w grafie \mathbf{G} wtedy i tylko wtedy, gdy zbiór krawędzi dualnych do krawędzi zbioru C jest rozcięciem grafu \mathbf{G}^* .
Dowód
Niech C będzie cyklem w grafie \mathbf{G} . W grafie płaskim cykl dzieli płaszczyznę \mathbb{R}^2 na dwie spójne części A_1 oraz A_0 , przy czym załóżmy, że A_1 jest ograniczona przez C , a A_0 jest nieograniczona. Niech f_1 będzie dowolną ścianą we wnętrzu A_1 , zaś f_0 ścianą nieskończoną, czyli zawartą w A_0 a v_1^*,v_0^* niech będą odpowiadającymi tym ścianom punktami grafu dualnego \mathbf{G}^* . Tak więc, v_1^*\in A_1 , a v_0^*\in A_0 . A zatem dowolnie wybrana droga P z v_1^* do v_0^* musi przeciąć cykl C co najmniej raz. Przecinające się krawędzie, jedna z drogi P i druga z cyklu C , są wzajemnie dualne (przy przejściu z \mathbf{G} do \mathbf{G}^{*} i z powrotem do \mathbf{G}^{**}\approx \mathbf{G} ). Tak więc, zbiór C^* krawędzi dualnych do krawędzi z cyklu C tworzy zbiór rozspajający wierzchołki v_1^*,v_0^* .
Pokażemy, że zbiór C^* jest rozcięciem, czyli minimalnym zbiorem rozspajającym. Zmniejszenie C^* powstaje oczywiście poprzez zmniejszenie zbioru C . Usunięcie jednakże krawędzi e z C , powoduje połączenie obszaru A_1 z obszarem A_0 . Pozwala to tworzyć krzywe łączące dowolne dwa punkty A_0\cup A_1 i nie przecinające krawędzi ze zbioru C-\lbrace e \rbrace . W konsekwencji pozwala to na tworzenie ścieżek między dowolnymi wierzchołkami grafu \mathbf{G}^* omijając krawędzie z C-\lbrace e \rbrace .
Dowód implikacji w drugą stronę jest analogiczny.