Matematyka dyskretna 1/Wykład 12: Grafy

From Studia Informatyczne

Czym jest graf



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{G}=\left( V,E \right), 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{G}=\left( V,E \right), gdzie:

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

czyli dwu-elementowych podzbiorów V.



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{G} symbolem {\sf V}\!\left(\mathbf{G}\right) będziemy oznaczać jego zbiór wierzchołków, zaś symbolem {\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{G} to liczba krawędzi incydentnych z v. Stopień wierzchołka v oznaczany jest jako {\sf deg}\ v.

Obserwacja 12.1

Jeśli \mathbf{G}=\left( V,E \right) jest grafem ogólnym, to


\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{G} miałby nieparzyście wiele wierzchołków o nieparzystym stopniu to suma \displaystyle\sum_{v\in V}{\sf deg}\ v byłaby nieparzysta, wbrew temu, że jest liczbą parzystą 2\left\vert E \right\vert.

image:End_of_proof.gif


Ściągnięcie zbioru \left\lbrace p,q,r \right\rbrace do wierzchołku x


(a.) Digraf oraz (b.) jego graf szkieletowy
Uwaga

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

  • suma grafów \mathbf{G}_1\cup\mathbf{G}_2=\left( V_1\cup V_2,E_1\cup E_2 \right),
  • przecięcie grafów \mathbf{G}_1\cap\mathbf{G}_2=\left( V_1\cap V_2,E_1\cap E_2 \right),
  • różnica grafów \mathbf{G}_1-\mathbf{G}_2=\left( V_1- V_2,E_1- E_2 \right),
  • podgraf grafu \mathbf{G} to graf \mathbf{H}, w którym {\sf V}\!\left(\mathbf{H}\right)\subseteq{\sf V}\!\left(\mathbf{G}\right) i {\sf E}\!\left(\mathbf{H}\right)\subseteq{\sf E}\!\left(\mathbf{G}\right),
  • restrykcja grafu \mathbf{G} do podzbioru X\subseteq V to \mathbf{G}|_X=\left( X,\left\lbrace vw:v,w\in X \right\rbrace \right),
  • podgraf indukowany grafu \mathbf{G} to graf będący restrykcją grafu \mathbf{G},
  • iloraz grafu \mathbf{G} przez relację równoważności \theta\subseteq V\times V na zbiorze jego wierzchołków to graf postaci

\mathbf{G}/\theta=\left( V/\theta,\left\lbrace \left\lbrace v/\theta,w/\theta \right\rbrace:\left\lbrace v,w \right\rbrace\in E \right\rbrace \right),

  • ściągnięcie zbioru wierzchołków X\subseteq V w grafie \mathbf{G} to szczególny przypadek ilorazu \mathbf{G}/\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\lbrace \left\lbrace v \right\rbrace:v\in V- X \right\rbrace\cup\left\lbrace X \right\rbrace. 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,\ldots,X_k, to ściągając w grafie \mathbf{G} kolejno zbiory X_1,\ldots,X_k otrzymamy graf ilorazowy \mathbf{G}/\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{D}=\left( V,E \right), 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\!\longrightarrow\!\bullet\ w.

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

Przegląd niektórych grafów



Antyklika \mathcal{A}_{5}




Graf nie będący dwudzielnym (a), niepełny graf dwudzielny (b) oraz pełny graf dwudzielny \mathcal{K}_{3,4} (c)


Klika \mathcal{K}_{5}




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 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}=\left( V,E \right), 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 \left( V_1\cup V_2,E \right). 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}=\left( V_1\cup V_2,E \right), 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}}=\left( \overline{V},\overline{E} \right), 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.

 

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



Grafy marszruta

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}=\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{G}=\left(V,E\right) 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.



Grafy spójne skladowe

Graf z rysunku Grafy spojne skladowe ma trzy spójne składowe: \left\lbrace v,w,y,x \right\rbrace,\left\lbrace u,z \right\rbrace,\left\lbrace t \right\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}=\left(V,E\right) możemy wymusić jedynie \left\vert V \right\vert-1 krawędzi. Z drugiej jednak strony, gdy graf \mathbf{G} ma więcej niż \left\vert V \right\vert\cdot(\left\vert V \right\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}=\left(V,E\right) o k składowych spójnych liczba jego krawędzi spełnia nierówności


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


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

  • istnieje graf prosty \mathbf{G}=\left(V,E\right) o dokładnie k składowych spójnych, w którym \left\vert E \right\vert= \left\vert V \right\vert-k,
  • istnieje graf prosty \mathbf{G}=\left(V,E\right) o dokładnie k składowych spójnych, w którym \left\vert E \right\vert= \frac{(\left\vert V \right\vert-k)(\left\vert V \right\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) =\left\vert V \right\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 \left\vert V \right\vert-k wierzchołków tworzy klikę \mathcal{K}_{n-k}, ma dokładnie \frac{(\left\vert V \right\vert-k)(\left\vert V \right\vert-k+1)}{2} krawędzi.
image:End_of_proof.gif


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)


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{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}=\left(V,E\right) następujące warunki są równoważne:

  1. \mathbf{T} jest drzewem,
  2. \mathbf{T} nie zawiera cykli i ma \left\vert V \right\vert-1 krawędzi,
  3. \mathbf{T} jest spójny i ma \left\vert V \right\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 \left\vert V \right\vert grafu \mathbf{T}. Oczywiście dla \left\vert V \right\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=\left\vert V \right\vert oraz 0<n_1,n_2<\left\vert V \right\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


\left\vert E \right\vert=(n_1-1)+(n_2-1)+1=\left\vert V \right\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 \left\vert E \right\vert=\left\vert V \right\vert-1.

3. \Rightarrow 4. Usunięcie dowolnej krawędzi spowoduje, że nowy graf będzie miał \left\vert V \right\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.

image:End_of_proof.gif

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}=\left(V,E\right) o k składowych spójnych posiada \left\vert E \right\vert=\left\vert V \right\vert-k krawędzi.