Ścieżki, Cykle, oraz Spójność

Marszruta w grafie \( \mathbf{G} \) z wierzchołka \( w \) do wierzchołka \( u \) to skończony ciąg krawędzi w postaci \( w v_1,v_1 v_2,\ldots,v_{k-1} u \).
W skrócie marszrutę taką oznaczamy przez \( w\to v_1\to v_2\to\ldots\to v_{k-1}\to u \).
Wierzchołek \( w \) nazywać będziemy początkowym, a \( u \) końcowym wierzchołkiem marszruty.

Długość marszruty \( w\to v_1\to v_2\to\ldots\to v_{k-1}\to u \) to liczba jej krawędzi.

Marszruta zamknięta to marszruta kończąca się w punkcie wyjścia, czyli taka, w której \( w=u \).

Uwaga

Marszruta może być również zdefiniowana w grafach skierowanych. Definiuje się ją analogicznie, uwzględniając jednak kierunek krawędzi. Marszruta taka, zgodna z kierunkiem krawędzi nazywana jest marszrutą skierowaną.

W grafie z rysunku Grafy marszruta ciąg \( u\to v\to w\to z\to z\to y\to v\to w\to v \) jest marszrutą z \( u \) do \( v \) o długości \( 8 \). Widzimy, że niektóre jej wierzchołki, a nawet krawędzie, powtarzają się. Wygodnie jest móc wyróżniać marszruty bez powtarzających się wierzchołków.

Droga to marszruta bez powtarzających się wierzchołków. Droga nazywana jest też często ścieżką.

Cykl to marszruta zamknięta, w której jedynym powtarzającym się wierzchołkiem jest jej początek (będący oczywiście również jej końcem).

W grafie z rysunku Grafy marszruta marszruta \( y\to v\to w\to u\to x \) jest drogą, zaś marszruta \( x\to u\to v\to w\to y\to x \) jest cyklem.
Czasem wygodnie jest traktować marszrutę w grafie \( \mathbf{G} \) (a więc w szczególności również cykle i ścieżki) jako podgraf

\( \mathbf{M}=( {\sf V}\!(\mathbf{M}),{\sf E}\!(\mathbf{M}) ) :=( \lbrace v_0,\ldots,v_k \rbrace,\lbrace \lbrace v_0,v_1 \rbrace,\ldots,\lbrace v_{k-1},v_k \rbrace \rbrace ). \)

Graf spójny to graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga. Graf niespójny to graf, który nie jest spójny.

Spójna składowa grafu \( \mathbf{G}=(V,E) \) to maksymalny (w sensie inkluzji) podzbiór \( X\subseteq V \), indukujący graf spójny \( \mathbf{G}|_X \).

Graf z rysunku Grafy marszruta jest spójny.

Uwaga

Dowolnym graf \( \mathbf{G} \) rozpada się na spójne składowe, tworzące podział zbioru \( V \). Grafy spójne mają jedynie jedną spójną składową, w przeciwieństwie do grafów niespójnych posiadających ich więcej.
Rozkład na spójne składowe wyznacza relacją równoważności \( \sigma\subseteq V \times V \), dla której graf ilorazowy \( \mathbf{G}/\sigma \) jest antykliką.

Wierzchołek izolowany to wierzchołek nie posiadający sąsiadów.

Uwaga

Punkty izolowane tworzą jednoelemetowe spójne składowe.

Graf z rysunku Grafy spojne skladowe ma trzy spójne składowe: \( \lbrace v,w,y,x \rbrace,\lbrace u,z \rbrace,\lbrace t \rbrace \). Ponadto \( t \) jest punktem izolowanym.

Intuicyjnie wydaje się, że graf spójny powinien mieć dostatecznie dużo krawędzi w stosunku do liczby wierzchołków. Okazuje się jednak, że w grafie spójnym \( \mathbf{G}=(V,E) \) możemy wymusić jedynie \( \vert V \vert-1 \) krawędzi. Z drugiej jednak strony, gdy graf \( \mathbf{G} \) ma więcej niż \( \vert V \vert\cdot(\vert V \vert-1)/2 \) krawędzi, to musi być spójny. Rezultaty te można uzyskać z bardziej ogólnego wyniku:

Twierdzenie 12.2

W grafie prostym \( \mathbf{G}=(V,E) \) o \( k \) składowych spójnych liczba jego krawędzi spełnia nierówności

\( \vert V \vert-k\leq \vert E \vert\leq\frac{(\vert V \vert-k)(\vert V \vert-k+1)}{2}. \)

Ponadto, są to najlepsze możliwe ograniczenia, tzn.

• istnieje graf prosty \( \mathbf{G}=(V,E) \) o dokładnie \( k \) składowych spójnych, w którym \( \vert E \vert= \vert V \vert-k \),
• istnieje graf prosty \( \mathbf{G}=(V,E) \) o dokładnie \( k \) składowych spójnych, w którym \( \vert E \vert= \frac{(\vert V \vert-k)(\vert V \vert-k+1)}{2} \).

Dowód

Niech \( n \) będzie liczbą wierzchołków grafu \( \mathbf{G} \), a \( m \) liczbą jego krawędzi. Dowód nierówności \( n-k\leq m \) przeprowadzimy indukcyjnie względem liczby krawędzi \( m \) w grafie \( \mathbf{G} \). Jeżeli \( m=0 \), to wszystkie wierzchołki są punktami izolowanymi czyli \( k=n \), co spełnia żądaną nierówność. Przy \( m>0 \) usunięcie krawędzi może nie zmienić liczby składowych spójnych albo zwiększyć ją o jeden. W pierwszym przypadku z założenia indukcyjnego dostaniemy odrazu że \( n-k\leq m-1\leq m \), zaś w drugim, założenie indukcyjne daje \( n-(k+1)\leq m-1 \), czyli rzeczywiście \( n-k\leq m \).

Dla dowodu górnego ograniczenia \( m\leq (n-k)(n-k+1)/2 \) na liczbę krawędzi załóżmy, że \( \mathbf{G} \) posiada \( k \) składowych spójnych i ma największą możliwą liczbę krawędzi wśród \( n \)-elementowych grafów o \( k \) składowych spójnych. Wtedy każda z tych składowych jest grafem pełnym, jako że inaczej moglibyśmy dołożyć krawędzie w takiej niepełnej składowej, nie zmieniając przy tym liczb \( k \) i \( n \). Pokażemy dodatkowo, że co najwyżej jedna z tych składowych może mieć więcej niż jeden wierzchołek. Istotnie, gdyby były dwie składowe \( V_1, V_2 \) o odpowiednio \( n_1 \geq n_2 >1 \) wierzchołkach, to - nie zmieniając pozostałych składowych, i - przenosząc jeden wierzchołek z \( V_2 \) do \( V_1 \) otrzymalibyśmy nowy graf. W oryginalnym grafie sumaryczna liczba krawędzi w (pełnych) składowych \( V_1, V_2 \) wynosi \( {{n_1}\choose{2}} + {{n_2}\choose{2}}, \) a w nowym grafie te zmodyfikowane (również pełne) składowe posiadają łącznie \( {{n_1+1}\choose{2}} + {{n_2-1}\choose{2}} \) krawędzi. Różnica między nową a starą liczbą krawędzi wynosi więc

\( \frac{(n_1+1)n_1 + (n_2-1)(n_2-2) - n_1(n_1-1) - n_2(n_2-1)}{2} = n_1 - n_2 +1 \geq 1 \)

co pokazuje, że nowy graf ma przynajmniej o jedną krawędź więcej. Dowodzi to, że graf \( \mathbf{G} \) maksymalizujący liczbę krawędzi ma opisaną przez nas własność. To z kolei oznacza, że \( k-1 \) jego składowych ma po jednym elemencie, a pozostała składowa jest grafem pełnym o \( n -(k-1) \) elementach. Taki graf ma oczywiście \( {{n-k+1}\choose{2}} \) krawędzi.

Aby zobaczyć, że podanych ograniczeń na liczbę krawędzi nie można poprawić zauważmy, że

• graf o \( k \) składowych spójnych, z których każda jest indukowaną ścieżką o liczności odpowiednio \( n_1,n_2,\ldots,n_k \) ma dokładnie \( (n_1-1)+(n_2-1)+\ldots+(n_k-1) =\vert V \vert-k \) krawędzi.
• rozważany w dowodzie graf o dokładnie \( k \) składowych spójnych, z których \( k-1 \) to wierzchołki izolowane, a pozostałe \( \vert V \vert-k \) wierzchołków tworzy klikę \( \mathcal{K}_{n-k} \), ma dokładnie \( \frac{(\vert V \vert-k)(\vert V \vert-k+1)}{2} \) krawędzi.

Las to graf nie zawierający cykli jako podgrafy.

Drzewo to graf spójny nie zawierający cykli, czyli spójny las.

Liść drzewa to wierzchołek o stopniu \( 1 \).

Gwiazda to drzewo, w którym co najwyżej jeden wierzchołek nie jest liściem.

Drzewo rozpinające grafu \( \mathbf{G} \) to podgraf grafu \( \mathbf{G} \) zawierający wszystkie jego wierzchołki i będący drzewem.

Drzewa można zdefiniować na kilka równoważnych sposobów:

Twierdzenie 12.3

Dla grafu \( \mathbf{T}=(V,E) \) następujące warunki są równoważne:

1. \( \mathbf{T} \) jest drzewem,
2. \( \mathbf{T} \) nie zawiera cykli i ma \( \vert V \vert-1 \) krawędzi,
3. \( \mathbf{T} \) jest spójny i ma \( \vert V \vert-1 \) krawędzi,
4. \( \mathbf{T} \) jest spójny, zaś usunięcie dowolnej krawędzi tworzy dokładnie dwie składowe,
5. dowolne dwa wierzchołki grafu \( \mathbf{T} \) są połączone dokładnie jedną drogą,
6. \( \mathbf{T} \) nie zawiera cykli, lecz dodanie dowolnej nowej krawędzi tworzy dokładnie jeden cykl.

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków \( \vert V \vert \) grafu \( \mathbf{T} \). Oczywiście dla \( \vert V \vert=1 \) graf \( \mathbf{T} \) nie ma krawędzi i tym samym spełnia wszystkie sześć warunków dowodzonego Twierdzenia.

1. \( \Rightarrow \) 2. Ponieważ \( \mathbf{T} \) nie posiada cykli, to usunięcie krawędzi rozspaja \( \mathbf{T} \) na dwa drzewa: pierwsze o \( n_1 \) wierzchołkach oraz drugie o \( n_2 \), przy czym \( n_1+n_2=\vert V \vert \) oraz \( 0 < n_1,n_2 < \vert V \vert \). Założenie indukcyjne gwarantuje, że nowo powstałe drzewa mają odpowiednio \( n_1-1 \) oraz \( n_2-1 \) krawędzi. Sumując te krawędzie wraz z usuniętą otrzymujemy

\( \vert E \vert=(n_1-1)+(n_2-1)+1=\vert V \vert-1. \)

2. \( \Rightarrow \) 3. Jeżeli \( \mathbf{T} \) nie byłby spójny, to miałby \( k\geq 2 \) składowych spójnych. Ponieważ żadna składowa nie ma cykli, założenie indukcyjne daje, że w każdej z \( k \) składowych krawędzi jest o jedną mniej niż wierzchołków. A więc, w całym grafie krawędzi jest o \( k \geq 2 \) mniej niż wierzchołków co daje sprzeczność z \( \vert E \vert=\vert V \vert-1 \).

3. \( \Rightarrow \) 4. Usunięcie dowolnej krawędzi spowoduje, że nowy graf będzie miał \( \vert V \vert-2 \) krawędzie. Na mocy Twierdzenia 12.2 okazuje się, że jest to za mało aby graf był spójny.

4. \( \Rightarrow \) 5. Jeżeli istniałyby dwie różne ścieżki \( P_1 \) oraz \( P_2 \) o wspólnym początku i końcu, to usunięcie krawędzi \( e\in P_1-P_2 \) nierozspajałoby grafu \( \mathbf{T} \).

5. \( \Rightarrow \) 6. Pomiędzy dwoma punktami dowolnego cyklu \( C \) istnieją dwie rozłączne ścieżki zawarte w \( C \). Tak więc istnienie dokładnie jednej ścieżki pomiędzy dowolnymi punktami w \( \mathbf{T} \) wyklucza istnienie cykli w \( \mathbf{T} \). Z drugiej zaś strony dodanie dodatkowej krawędzi \( uv \) stworzy cykl składający się z krawędzi \( uv \) oraz ścieżki łączącej wierzchołek \( u \) z \( v \) zawartej w grafie \( \mathbf{T} \). Powyższy cykl jest jedyny. Wynika to z tego, że jeżeli istnieją dwa cykle zawierające krawędź \( uv \), to musi istnieć trzeci cykl niezawierajacy \( uv \), czyli zawarty w \( \mathbf{T} \) co nie jest możliwe.

6. \( \Rightarrow \) 1. Gdyby, mimo spełniania warunku 6, graf \( \mathbf{T} \) nie był spójny, to dodanie jednej krawędzi łączącej dwa wierzchołki w różnych składowych spójnych nie utworzy cyklu.

Z charakteryzacji drzew podanej w Twierdzeniu 12.3 natychmiast dostajemy następujący związek miedzy liczbą krawędzi i wierzchołków w dowolnym lesie.

Wniosek 12.4

Każdy las \( \mathbf{G}=(V,E) \) o \( k \) składowych spójnych posiada \( \vert E \vert=\vert V \vert-k \) krawędzi.

Przegląd niektórych grafów

Graf pusty to graf bez krawędzi. Antyklika lub graf niezależny to inne nazwy grafu pustego. Antyklikę o \( n \) wierzchołkach oznaczać będziemy przez \( \mathcal{A}_{n} \).

Graf pełny to graf, w którym każde dwa wierzchołki połączone są krawędzią. Graf pełny nazywany jest także kliką i oznaczany przez \( \mathcal{K}_{n} \), gdzie \( n \) jest liczbą jego wierzchołków.

Uwaga

Liczba krawędzi w klice \( \mathcal{K}_{n} \) wynosi \( \frac{n(n-1)}{2} \).

Graf dwudzielny to graf \( \mathbf{G}=( V,E ) \), w którym zbiór \( V \) da się podzielić na dwa rozłączne podzbiory \( V_1 \) oraz \( V_2 \) tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru \( V_i \) nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez \( ( V_1\cup V_2,E ) \). Zauważmy jednak, że podział taki nie jest jednoznaczny -- np. w antyklice \( \mathcal{A}_{n} \) dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Pełny graf dwudzielny to graf dwudzielny \( \mathbf{G}=( V_1\cup V_2,E ) \), w którym każdy wierzchołek z \( V_1 \) jest połączony z każdym wierzchołkiem z \( V_2 \). Pełny graf dwudzielny oznaczać będziemy przez \( \mathcal{K}_{r,s} \), gdzie \( r \) jest rozmiarem \( V_1 \), a \( s \) rozmiarem \( V_2 \).

Graf płaski to para \( \mathbf{\overline{G}}=( \overline{V},\overline{E} ) \), gdzie:

• \( \overline{V} \) jest jakimś zbiorem punktów płaszczyzny \( \mathbb{R}^2 \),

• \( \overline{E} \) jest zbiorem nie przecinających się odcinków lub łuków w \( R^2 \) o końcach ze zbiorze \( \overline{V} \).

Graf planarny to graf, który jest prezentowalny jako graf płaski.