Informatyka MIMUW

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.