Matematyka dyskretna 1/Wykład 12: Grafy

Czym jest graf

<flash>file=Grafy mapa samochodowa.swf|width=250|height=250</flash>

<div.thumbcaption>Bardzo uproszczona mapa samochodowa Polski

Wyruszając w daleką podróż zabieramy ze sobą mapę samochodową. Głównymi elementami graficznymi zawartymi w mapie są punkty (małe kółka) symbolizujące miasta, oraz odcinki (lub łuki) obrazujące drogi pomiędzy nimi. Taka mapa jest z grubsza przedstawieniem rzeczywistości za pomocą grafu. Chcąc na przykład znaleźć drogę z Bydgoszczy do Krakowa, szukamy ciągu kolejno połączonych miast zaczynającego się w Bydgoszczy i kończącego się w Krakowie. Jest to nic innego, jak znalezienie odpowiedniej ścieżki w grafie połączeń między miastami.

Graf to para $\mathbf{𝐆}=(V,E)$, gdzie:

• $V$ jest zbiorem wierzchołków,
  

(czasami zwanymi węzłami lub punktami grafu)

• $E$ jest rodziną (być może powtarzających się) krawędzi,
  

czyli jedno- i dwu-elementowych podzbiorów $V$.

Graf prosty to para $\mathbf{𝐆}=(V,E)$, gdzie:

• $V$ jest zbiorem wierzchołków,
• $E$ jest zbiorem krawędzi między różnymi wierzchołkami,
  

czyli dwu-elementowych podzbiorów $V$.

<flashwrap>file=Grafy graf ogolny i prosty.swf|size=small</flashwrap>

<div.thumbcaption>Graf ogólny (a.) oraz prosty (b.)

Uwaga

W grafie w odróżnieniu od grafu prostego dopuszczamy pętle oraz krawędzie wielokrotne. Wierzchołek nazywany jest czasem także węzłem, jak i punktem grafu. Krawędź łącząca $v$ z $w$ oznaczana będzie jako $vw$. Jeśli istnieje krawędź $vw$ to mówimy, że $v$ i $w$ są sąsiadami; oraz że krawędź $vw$ jest incydentna do $v$ ($w$). Ponadto, dla grafu $\mathbf{𝐆}$ symbolem Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{G}\right)} będziemy oznaczać jego zbiór wierzchołków, zaś symbolem Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf E}\!\left(\mathbf{G}\right)} jego zbiór krawędzi. Czasem, dla odróżnienia grafu od grafu prostego, graf będziemy nazywać też grafem ogólnym.

Stopień wierzchołka $v$ w grafie $\mathbf{𝐆}$ to liczba krawędzi incydentnych z $v$. Stopień wierzchołka $v$ oznaczany jest jako Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ v} .

Obserwacja 12.1

Jeśli $\mathbf{𝐆}=(V,E)$ jest grafem ogólnym, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{v\in V}{\sf deg}\ v=2\left\vert E \right\vert. }

A zatem liczba wierzchołków o nieparzystym stopniu jest parzysta.

Dowód

Każda krawędź jest incydentna do dwóch wierzchołków. Zliczając krawędzie incydentne do kolejnych wierzchołków, a następnie sumując te wartości, każda krawędź $vw$ zostanie zliczona dwa razy: raz przy rozpatrywaniu wierzchołka $v$, a drugi raz przy $w$.

Jeśli $\mathbf{𝐆}$ miałby nieparzyście wiele wierzchołków o nieparzystym stopniu to suma Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{v\in V}{\sf deg}\ v} byłaby nieparzysta, wbrew temu, że jest liczbą parzystą $2\left|E\right|$.

<flashwrap>file=Grafy sciagniecie.swf|size=small</flashwrap>

<div.thumbcaption>Ściągnięcie zbioru $\{p,q,r\}$ do wierzchołku $x$

<flashwrap>file=Grafy digraf.swf|size=small</flashwrap>

<div.thumbcaption>(a.) Digraf oraz (b.) jego graf szkieletowy

Uwaga

Dla grafów $\mathbf{𝐆}=(V,E)$, ${\mathbf{𝐆}}_1=(V_1,E_1)$, ${\mathbf{𝐆}}_2=(V_2,E_2)$ definiujemy następujące pojęcia:

• suma grafów ${\mathbf{𝐆}}_1\cup {\mathbf{𝐆}}_2=(V_1\cup V_2,E_1\cup E_2)$,

• przecięcie grafów ${\mathbf{𝐆}}_1\cap {\mathbf{𝐆}}_2=(V_1\cap V_2,E_1\cap E_2)$,

• różnica grafów ${\mathbf{𝐆}}_1-{\mathbf{𝐆}}_2=(V_1-V_2,E_1-E_2)$,

• podgraf grafu $\mathbf{𝐆}$ to graf $\mathbf{𝐇}$, w którym Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{H}\right)\subseteq{\sf V}\!\left(\mathbf{G}\right)} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf E}\!\left(\mathbf{H}\right)\subseteq{\sf E}\!\left(\mathbf{G}\right)} ,

• restrykcja grafu $\mathbf{𝐆}$ do podzbioru $X\subseteq V$ to $\mathbf{𝐆}{|}_X=(X,\{vw:v,w\in X\})$,

• podgraf indukowany grafu $\mathbf{𝐆}$ to graf będący restrykcją grafu $\mathbf{𝐆}$,

• iloraz grafu $\mathbf{𝐆}$ przez relację równoważności $\theta \subseteq V\times V$ na zbiorze jego wierzchołków to graf postaci

$\mathbf{𝐆}/\theta =(V/\theta ,\{\{v/\theta ,w/\theta \}:\{v,w\}\in E\}),$

• ściągnięcie zbioru wierzchołków $X\subseteq V$ w grafie $\mathbf{𝐆}$ to szczególny przypadek ilorazu $\mathbf{𝐆}/\theta$, w którym klasy równoważności wszystkich wierzchołków spoza $X$ są jednoelementowe, a $X$ stanowi dodatkową klasę, tzn. $V/\theta =\{\left\{v\right\}:v\in V-X\}\cup \left\{X\right\}$. W ten sposób zbiór $X$ został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z $X$. Z drugiej strony, jeśli $\theta \subseteq V\times V$ jest relacją równoważności o klasach $X_1,\dots ,X_k$, to ściągając w grafie $\mathbf{𝐆}$ kolejno zbiory $X_1,\dots ,X_k$ otrzymamy graf ilorazowy $\mathbf{𝐆}/\theta$.

W dotychczasowej interpretacji grafów, jako mapy dróg zakładaliśmy, że istnienie drogi np. z Krakowa do Zakopanego, gwarantowało także możliwość powrotu po tej samej trasie. To oczywiście nie musi być zawsze prawdą, np. w miastach jest wiele dróg jednokierunkowych. Chcąc rozważać również takie jednokierunkowe trasy, tzn uwzględniać kierunek relacji między dwoma obiektami, będziemy mówić o grafach skierowanych.

Graf skierowany (lub inaczej digraf) to para $\mathbf{𝐃}=(V,E)$, gdzie

• $V$ jest zbiorem wierzchołków,

• $E$ jest zbiorem krawędzi skierowanych, czyli $E\subseteq V\times V$.

Uwaga

Krawędź digrafu (czyli uporządkowaną parę) $vw$ graficznie przedstawiamy jako strzałkę $v\bullet ⟶\bullet w$.

Graf szkieletowy digrafu $\mathbf{𝐃}$ to graf otrzymany z $\mathbf{𝐃}$ poprzez zaniedbanie (usunięcie) kierunku krawędzi, ale nie samych krawędzi.

Przegląd niektórych grafów

<flash>file=Grafy antyklika.swf|width=250|height=250</flash>

<div.thumbcaption>Antyklika ${{𝒜}}_5$

<flash>file=Grafy dwudzielne.swf|width=250|height=250</flash> <div.thumbcaption>Graf nie będący dwudzielnym (a), niepełny graf dwudzielny (b)

oraz pełny graf dwudzielny ${{𝒦}}_{3,4}$ (c)

<flash>file=Grafy klika.swf|width=250|height=250</flash>

<div.thumbcaption>Klika ${{𝒦}}_5$

<flashwrap>file=Grafy planarne.swf|size=small</flashwrap>

<div.thumbcaption>Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c)

Graf pusty to graf bez krawędzi. Antyklika lub graf niezależny to inne nazwy grafu prostego. Antyklikę o $n$ jest ilością wierzchołkach oznaczać będziemy przez ${{𝒜}}_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 ${{𝒦}}_n$, gdzie $n$ jest liczbą jego wierzchołków.

Uwaga

Liczba krawędzi w klice ${{𝒦}}_n$ wynosi $\frac{n(n-1)}{2}$.

Graf dwudzielny to graf $\mathbf{𝐆}=(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 ${{𝒜}}_n$ dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Pełny graf dwudzielny to graf dwudzielny $\mathbf{𝐆}=(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 ${{𝒦}}_{r,s}$, gdzie $r$ jest rozmiarem $V_1$, a $s$ rozmiarem $V_2$.

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

• $\bar{V}$ jest jakimś zbiorem punktów płaszczyzny ${\mathbb{ℝ}}^2$,
• $\bar{E}$ jest zbiorem nie przecinających się odcinków lub łuków w $R^2$

o końcach ze zbiorze $\bar{V}$.

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

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

<flashwrap>file=Grafy marszruta.swf|size=small</flashwrap>

<div.thumbcaption>Grafy marszruta

Marszruta w grafie $\mathbf{𝐆}$ z wierzchołka $w$ do wierzchołka $u$ to skończony ciąg krawędzi w postaci $w{v}_1,v_1{v}_2,\dots ,v_{k-1}u$.
W skrócie marszrutę taką oznaczamy przez $w\to v_1\to v_2\to \dots \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 \dots \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 Uzupelnic pict 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 Uzupelnic pict 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{𝐆}$ (a więc w szczególności również cykle i ścieżki) jako podgraf

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{M}=\left( {\sf V}\!\left(\mathbf{M}\right),{\sf E}\!\left(\mathbf{M}\right) \right) :=\left( \left\lbrace v_0,\ldots,v_k \right\rbrace,\left\lbrace \left\lbrace v_0,v_1 \right\rbrace,\ldots,\left\lbrace v_{k-1},v_k \right\rbrace \right\rbrace \right). }

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{𝐆}=(V,E)$ to maksymalny (w sensie inkluzji) podzbiór $X\subseteq V$, indukujący graf spójny $\mathbf{𝐆}{|}_X$.

Graf z rysunku Uzupelnic pict marszruta| jest spójny.

Uwaga

Dowolnym graf $\mathbf{𝐆}$ 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{𝐆}/\sigma$ jest antykliką.

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

Uwaga

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

{grafy_spojne_skladowe} { [Rysunek z pliku: grafyspojneskladowe.eps]}

Graf z rysunku Uzupelnic pict spojne skladowe| ma trzy spójne składowe: $\{v,w,y,x\},\{u,z\},\left\{t\right\}$. 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{𝐆}=(V,E)$ możemy wymusić jedynie $\left|V\right|-1$ krawędzi. Z drugiej jednak strony, gdy graf $\mathbf{𝐆}$ ma więcej niż $\left|V\right|\cdot (\left|V\right|-1)/2$ krawędzi, to musi być spójny. Rezultaty te można uzyskać z bardziej ogólnego wyniku:

Twierdzenie 2

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

$\left|V\right|-k\le \left|E\right|\le \frac{(\left|V\right|-k)(\left|V\right|-k+1)}{2}.$

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

• istnieje graf prosty $\mathbf{𝐆}=(V,E)$ o dokładnie $k$

składowych spójnych, w którym $\left|E\right|=\left|V\right|-k$,

• istnieje graf prosty $\mathbf{𝐆}=(V,E)$ o dokładnie $k$

składowych spójnych, w którym $\left|E\right|=\frac{(\left|V\right|-k)(\left|V\right|-k+1)}{2}$.

Dowód

Niech $n$ będzie liczbą wierzchołków grafu $\mathbf{𝐆}$, a $m$ liczbą jego krawędzi. Dowód nierówności $n-k\le m$ przeprowadzimy indukcyjnie względem liczby krawędzi $m$ w grafie $\mathbf{𝐆}$. 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\le m-1\le m$, zaś w drugim, założenie indukcyjne daje $n-(k+1)\le m-1$, czyli rzeczywiście $n-k\le m$.

Dla dowodu górnego ograniczenia $m\le (n-k)(n-k+1)/2$ na liczbę krawędzi załóżmy, że $\mathbf{𝐆}$ 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\ge 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 $(\genfrac{}{}{0ex}{}{n_1}{2})+(\genfrac{}{}{0ex}{}{n_2}{2}),$ a w nowym grafie te zmodyfikowane (również pełne) składowe posiadają łącznie $(\genfrac{}{}{0ex}{}{n_1+1}{2})+(\genfrac{}{}{0ex}{}{n_2-1}{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\ge 1$

co pokazuje, że nowy graf ma przynajmniej o jedną krawędź więcej. Dowodzi to, że graf $\mathbf{𝐆}$ 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 $(\genfrac{}{}{0ex}{}{n-k+1}{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,\dots ,n_k$ ma dokładnie $(n_1-1)+(n_2-1)+\dots +(n_k-1)=\left|V\right|-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 $\left|V\right|-k$ wierzchołków tworzy klikę ${{𝒦}}_{n-k}$, ma dokładnie $\frac{(\left|V\right|-k)(\left|V\right|-k+1)}{2}$ krawędzi.

<flash>file=Grafy las.swf|width=300|height=150</flash> <div.thumbcaption>Drzewo (a); las nie będący drzewem ale z dwiema gwiazdami jako składowymi spójnymi (b);

oraz graf nie będący lasem (c)

<flash>file=Grafy drzewo rozp.swf|width=250|height=250</flash>

<div.thumbcaption>Drzewo rozpinające

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{𝐆}$ to podgraf grafu $\mathbf{𝐆}$ zawierający wszystkie jego wierzchołki i będący drzewem.

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

Twierdzenie 3

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

1. $\mathbf{𝐓}$ jest drzewem,
2. $\mathbf{𝐓}$ nie zawiera cykli i ma $\left|V\right|-1$ krawędzi,
3. $\mathbf{𝐓}$ jest spójny i ma $\left|V\right|-1$ krawędzi,
4. $\mathbf{𝐓}$ jest spójny, zaś usunięcie dowolnej krawędzi tworzy dokładnie dwie składowe,
5. dowolne dwa wierzchołki grafu $\mathbf{𝐓}$ są połączone dokładnie jedną drogą,
6. $\mathbf{𝐓}$ 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 $\left|V\right|$ grafu $\mathbf{𝐓}$. Oczywiście dla $\left|V\right|=1$ graf $\mathbf{𝐓}$ nie ma krawędzi i tym samym spełnia wszystkie sześć warunków dowodzonego Twierdzenia.

1. $\Rightarrow$ 2. Ponieważ $\mathbf{𝐓}$ nie posiada cykli, to usunięcie krawędzi rozspaja $\mathbf{𝐓}$ na dwa drzewa: pierwsze o $n_1$ wierzchołkach oraz drugie o $n_2$, przy czym $n_1+n_2=\left|V\right|$ oraz $0<n_1,n_2<\left|V\right|$. 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

$\left|E\right|=(n_1-1)+(n_2-1)+1=\left|V\right|-1.$

2. $\Rightarrow$ 3. Jeżeli $\mathbf{𝐓}$ nie byłby spójny, to miałby $k\ge 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\ge 2$ mniej niż wierzchołków co daje sprzeczność z $\left|E\right|=\left|V\right|-1$.

3. $\Rightarrow$ 4. Usunięcie dowolnej krawędzi spowoduje, że nowy graf będzie miał $\left|V\right|-2$ krawędzie. Na mocy Twierdzenia Uzupelnic th oszacowanie E| 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{𝐓}$.

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{𝐓}$ wyklucza istnienie cykli w $\mathbf{𝐓}$. 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{𝐓}$. 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{𝐓}$ co nie jest możliwe.

6. $\Rightarrow$ 1. Gdyby, mimo spełniania warunku 6, graf $\mathbf{𝐓}$ 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 Uzupelnic th warunki na drzewo| natychmiast dostajemy następujący związek miedzy liczbą krawędzi i wierzchołków w dowolnym lesie.

Wniosek

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