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.
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
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:
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.