Matematyka dyskretna 1/Wykład 12: Grafy

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 , gdzie:

  • jest zbiorem wierzchołków,

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

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

czyli jedno- i dwu-elementowych podzbiorów .

Graf prosty to para , gdzie:

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

czyli dwu-elementowych podzbiorów .

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 z oznaczana będzie jako . Jeśli istnieje krawędź to mówimy, że i są sąsiadami; oraz że krawędź jest incydentna do (). Ponadto, dla grafu symbolem będziemy oznaczać jego zbiór wierzchołków, zaś symbolem jego zbiór krawędzi. Czasem, dla odróżnienia grafu od grafu prostego, graf będziemy nazywać też grafem ogólnym.

Stopień wierzchołka w grafie to liczba krawędzi incydentnych z . Stopień wierzchołka oznaczany jest jako .

Obserwacja 12.1

Jeśli jest grafem ogólnym, to



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ź zostanie zliczona dwa razy: raz przy rozpatrywaniu wierzchołka , a drugi raz przy .

Jeśli miałby nieparzyście wiele wierzchołków o nieparzystym stopniu to suma byłaby nieparzysta, wbrew temu, że jest liczbą parzystą .

End of proof.gif
(a.) Digraf oraz (b.) jego graf szkieletowy
Uwaga

Dla grafów , , definiujemy następujące pojęcia:

  • suma grafów ,
  • przecięcie grafów ,
  • różnica grafów ,
  • podgraf grafu to graf , w którym i ,
  • restrykcja grafu do podzbioru to ,
  • podgraf indukowany grafu to graf będący restrykcją grafu ,
  • iloraz grafu przez relację równoważności na zbiorze jego wierzchołków to graf postaci

  • ściągnięcie zbioru wierzchołków w grafie to szczególny przypadek ilorazu , w którym klasy równoważności wszystkich wierzchołków spoza są jednoelementowe, a stanowi dodatkową klasę, tzn. . W ten sposób zbiór został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z . Z drugiej strony, jeśli jest relacją równoważności o klasach , to ściągając w grafie kolejno zbiory otrzymamy graf ilorazowy .

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 , gdzie

  • jest zbiorem wierzchołków,
  • jest zbiorem krawędzi skierowanych, czyli .
Uwaga

Krawędź digrafu (czyli uporządkowaną parę) graficznie przedstawiamy jako strzałkę .

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

Przegląd niektórych grafów

Antyklika

[[File:Grafy dwudzielne.svg|250x250px|thumb|left|Graf nie będący dwudzielnym (a), niepełny graf dwudzielny (b) oraz pełny graf dwudzielny (c)

Klika
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 wierzchołkach oznaczać będziemy przez .

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 , gdzie jest liczbą jego wierzchołków.

Uwaga

Liczba krawędzi w klice wynosi .

Graf dwudzielny to graf , w którym zbiór da się podzielić na dwa rozłączne podzbiory oraz tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez . Zauważmy jednak, że podział taki nie jest jednoznaczny -- np. w antyklice dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Pełny graf dwudzielny to graf dwudzielny , w którym każdy wierzchołek z jest połączony z każdym wierzchołkiem z . Pełny graf dwudzielny oznaczać będziemy przez , gdzie jest rozmiarem , a rozmiarem .


Graf płaski to para , gdzie:

  • jest jakimś zbiorem punktów płaszczyzny ,
  • jest zbiorem nie przecinających się odcinków lub łuków w o końcach ze zbiorze .

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

 

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

Marszruta w grafie z wierzchołka do wierzchołka to skończony ciąg krawędzi w postaci .
W skrócie marszrutę taką oznaczamy przez .
Wierzchołek nazywać będziemy początkowym, a końcowym wierzchołkiem marszruty.

Długość marszruty to liczba jej krawędzi.

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

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 jest marszrutą z do o długości . 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 jest drogą, zaś marszruta jest cyklem.
Czasem wygodnie jest traktować marszrutę w grafie (a więc w szczególności również cykle i ścieżki) jako podgraf

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 to maksymalny (w sensie inkluzji) podzbiór , indukujący graf spójny .

Graf z rysunku Grafy marszruta jest spójny.

Uwaga

Dowolnym graf rozpada się na spójne składowe, tworzące podział zbioru . 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 , dla której graf ilorazowy 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: . Ponadto 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 możemy wymusić jedynie krawędzi. Z drugiej jednak strony, gdy graf ma więcej niż krawędzi, to musi być spójny. Rezultaty te można uzyskać z bardziej ogólnego wyniku:

Twierdzenie 12.2

W grafie prostym o składowych spójnych liczba jego krawędzi spełnia nierówności



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

  • istnieje graf prosty o dokładnie składowych spójnych, w którym ,
  • istnieje graf prosty o dokładnie składowych spójnych, w którym .

Dowód

Niech będzie liczbą wierzchołków grafu , a liczbą jego krawędzi. Dowód nierówności przeprowadzimy indukcyjnie względem liczby krawędzi w grafie . Jeżeli , to wszystkie wierzchołki są punktami izolowanymi czyli , co spełnia żądaną nierówność. Przy 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 , zaś w drugim, założenie indukcyjne daje , czyli rzeczywiście .

Dla dowodu górnego ograniczenia na liczbę krawędzi załóżmy, że posiada składowych spójnych i ma największą możliwą liczbę krawędzi wśród -elementowych grafów o 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 i . 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 o odpowiednio wierzchołkach, to - nie zmieniając pozostałych składowych, i - przenosząc jeden wierzchołek z do otrzymalibyśmy nowy graf. W oryginalnym grafie sumaryczna liczba krawędzi w (pełnych) składowych wynosi a w nowym grafie te zmodyfikowane (również pełne) składowe posiadają łącznie krawędzi. Różnica między nową a starą liczbą krawędzi wynosi więc



co pokazuje, że nowy graf ma przynajmniej o jedną krawędź więcej. Dowodzi to, że graf maksymalizujący liczbę krawędzi ma opisaną przez nas własność. To z kolei oznacza, że jego składowych ma po jednym elemencie, a pozostała składowa jest grafem pełnym o elementach. Taki graf ma oczywiście krawędzi.

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

  • graf o składowych spójnych, z których każda jest indukowaną ścieżką o liczności odpowiednio ma dokładnie krawędzi.
  • rozważany w dowodzie graf o dokładnie składowych spójnych, z których to wierzchołki izolowane, a pozostałe wierzchołków tworzy klikę , ma dokładnie krawędzi.
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 .

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

Drzewo rozpinające grafu to podgraf grafu 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 następujące warunki są równoważne:

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

1. 2. Ponieważ nie posiada cykli, to usunięcie krawędzi rozspaja na dwa drzewa: pierwsze o wierzchołkach oraz drugie o , przy czym oraz . Założenie indukcyjne gwarantuje, że nowo powstałe drzewa mają odpowiednio oraz krawędzi. Sumując te krawędzie wraz z usuniętą otrzymujemy



2. 3. Jeżeli nie byłby spójny, to miałby składowych spójnych. Ponieważ żadna składowa nie ma cykli, założenie indukcyjne daje, że w każdej z składowych krawędzi jest o jedną mniej niż wierzchołków. A więc, w całym grafie krawędzi jest o mniej niż wierzchołków co daje sprzeczność z .

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

4. 5. Jeżeli istniałyby dwie różne ścieżki oraz o wspólnym początku i końcu, to usunięcie krawędzi nierozspajałoby grafu .

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

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

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 o składowych spójnych posiada krawędzi.