Opisywanie grafów

Na rysunku poniżej mamy przedstawiony jeden ze sposobów reprezentowania sieci społecznych:

Krawędź łącząca dwa imiona oznacza, że te dwie osoby znają się. Jeśli między jakimiś imionami nie ma krawędzi to jest to informacja, że osoby te nie znają się. Związek "znania się" reprezentowany w grafie jest dwustronny. Jeśli np. Audrey zna Gayla to również Gayle zna Audrey.

Omawiana tutaj sieć społeczna jest grafem. Imiona są tutaj wierzchołkami grafu. Odcinki łączące dwa wierzchołki to krawędzie grafu. Krawędź łączącą wierzchołki $u$‍ i $v$‍ oznaczamy za pomocą pary $(u,v)$‍. Ponieważ w przedstawionym tutaj grafie mamy do czynienia z relacją dwustronną to nasz graf jest grafem nieskierowanym. Nieskierowana krawędź $(u,v)$‍ to to samo co $(v,u)$‍. W dalszej części zobaczymy także grafy skierowane, w których związek pomiędzy wierzchołkami nie musi być obustronny. W grafie nieskierowanym krawędź pomiędzy dwoma wierzchołkami, jak np. ta łącząca Andrey i Gayla jest incydentna do tych dwóch wierzchołków. Mówimy również, że wierzchołki połączone krawędzią są adjacentne lub sąsiadujące. Liczbę krawędzi incydentnych z wierzchołkiem nazywamy stopniem wierzchołka.

Audrey i Frank nie znają się. Przyjmijmy, że Frank chciałby poznać Audrey. W jaki sposób mógłby się z nim poznać? Zna on Emily, która zna Billa, który z kolei zna Audrey. Mówimy, że istnieje ścieżka o długości trzech krawędzi pomiędzy Frankiem a Audrey. W rzeczywistości jest to najkrótsza ścieżka łącząca ich. Nie ma w tym grafie krótszej ścieżki pomiędzy nimi. Ścieżka pomiędzy dwoma wierzchołkami, która zawiera najmniejszą liczbę krawędzi nazywamy najkrótszą ścieżką. Na rysunku poniżej zaznaczyliśmy tę omówioną tutaj najkrótszą ścieżkę:

Kiedy ścieżka zaczyna się i kończy na tym samym wierzchołku, to nazywamy ją cyklem. Nasza sieć społeczna zawiera wiele cykli. Jeden z nich to: od Audrey do Billa do Jeffa do Harrego do Ilany i z powrotem do Audrey. Poniżej zaznaczyliśmy krótszy cykl, którego elementem jest Audrey. Mowa tu o cyklu od Audrey do Billa do Gayla i z powrotem do Audrey. Czy potrafisz w tym grafie znaleźć jeszcze jakieś cykle?

Czasami umieszczamy w grafach liczby obok krawędzi. Na przykład w sieci społecznej liczba obok krawędzi może oznaczać jak dobrze znają się dwie osoby. Przytoczmy jeszcze jeden przykład. Tym razem za pomocą grafu zaprezentujemy mapę drogową. Zakładając, że nie ma ulic jednokierunkowych, graf ten jest również nieskierowany. Wierzchołkami grafu są miasta, a krawędzie to ulice. Wartości przypisane do krawędzi oznaczają odległości między miastami. Poniżej mamy przykład takiej mapy drogowej (bez zachowanej skali). Mapa przedstawia fragment dróg międzystanowych pomiędzy miastami północno-wschodniej części Stanów Zjednoczonych. Do każdej krawędzi przypisano długość drogi:

Liczbę, której używamy do oznaczania krawędzi nazywamy jej wagą. Graf, którego krawędzie mają wagi nazywamy grafem ważonym. Dla mapy drogowej, jeśli chcemy znaleźć najkrótszą drogę pomiędzy dwoma miastami, będziemy szukać ścieżki pomiędzy dwoma krawędziami z najmniejszą sumą wag krawędzi. Tak samo jak w przypadku grafu nieważonego, ścieżkę o takiej własności będziemy nazywać najkrótszą ścieżką. I tak, dla naszego grafu, najkrótszą ścieżką pomiędzy Nowym Jorkiem a Concord będzie ta przechodząca przez New Haven, Hartford, Sturbridge, Weston oraz Reading. Suma wag dla tej ścieżki wyniesie 289 mil.

Związek pomiędzy wierzchołkami nie musi być obustronny. Na przykład możemy mieć mapę drogową zawierającą również drogi jednokierunkowe. Inny przykład to graf pokazujący kolejność z jaką powinien ubierać się bramkarz hokejowy:

Teraz krawędzie są skierowane i prezentowane graficznie za pomocą strzałek. Graf taki nazywamy skierowanym. W powyższym przykładzie kierunek krawędzi mówi, które części wyposażenia bramkarza powinny być zakładane przed innymi. I tak, krawędź od ochraniacza klatki piersiowej (chest pad) do swetra (sweater) wskazuje, że ochraniacz powinien być założony przed swetrem. Liczby obok wierzchołków pokazują jedną z możliwych kolejności z jaką można zakładać strój. I tak slipy powinno ubrać się jako pierwsze, następnie skarpety, spodenki uciskowe itd. aż do blokera. Mogłeś/aś zauważyć, że ten konkretny graf skierowany nie posiada cyklów. Taki graf nazywamy skierowanym grafem acyklicznym lub w skrócie dag (z ang. directed acyclic graph). Oczywiście możemy mieć do czynienia również ze skierowanym grafem ważonym, jak np. mapa z drogami jednokierunkowymi i oznaczonymi odległościami.

Z grafami skierowanymi związane jest nieco inne nazewnictwo. Dla skierowanej krawędzi, wierzchołek, z którego krawędź wychodzi nazywamy wierzchołkiem początkowym, wierzchołek, na którym krawędź się kończy jest nazywana wierzchołkiem końcowym. Na przykład wierzchołkiem początkowym dla jednej z krawędzi jest ochraniacz klatki piersiowej(chest pad), a wierzchołkiem końcowym jest sweter (sweater). Jeśli wierzchołkiem początkowym krawędzi jest wierzchołek $u$‍, a końcowym wierzchołek $v$‍, to krawędź taką oznaczamy $(u,v)$‍ i tutaj kolejność ma w tej parze ma znaczenie. Liczba krawędzi wychodzących z wierzchołka to stopień wychodzący wierzchołka ( ang. out-degree), a liczba krawędzi wchodzących do wierzchołka to stopień wchodzący wierzchołka (ang. in-degree).

Jak możesz sobie wyobrazić, grafy — zarówno te skierowane jak i nieskierowane — mają wiele zastosowań w przedstawianiu relacji w rzeczywistym świecie.

Podczas pracy z grafami wygodnie jest posługiwać się pojęciami zbioru wierzchołków i zbioru krawędzi. Zazwyczaj zbiór wszystkich wierzchołków grafu oznaczamy literą $V$‍, natomiast zbiór wszystkich krawędzi literą $E$‍. Gdy reprezentujemy graf lub gdy wykonujemy na nim jakiś algorytm, często chcemy wykorzystać liczbę wierzchołków i liczbę krawędzi w notacji asymptotycznej. I tak, przyjmijmy, że czas działania jakiegoś algorytmu jest liniowy względem liczby wierzchołków grafu. Możemy to zapisać ściśle, że czas ten jest $\mathrm{\Theta }(|V|)$‍, gdzie $|\cdot |$‍ to liczba elementów w zbiorze. Widać jednak, że używanie notacji liczności zbioru w notacji asymptotycznej jest nieczytelne. Dlatego też przyjmuje się, że w notacji asymptotycznej i tylko w notacji asymptotycznej będziemy pomijać oznaczenie liczności zbioru. Więc zamiast pisać $\mathrm{\Theta }(|V|)$‍, napiszemy po prostu $\mathrm{\Theta }(V)$‍. Podobnie zamiast $\mathrm{\Theta }(\lg |E|)$‍ będziemy stosować zapis $\mathrm{\Theta }(\lg E)$‍.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.