Teoria grafów

Graf = zbioru wierzchołków i krawędzi. Zazwyczaj zbiór wszystkich wierzchołków grafu oznaczamy literą VV, natomiast zbiór wszystkich krawędzi literą E.

Przykład grafu (żródło khanacademy.org):

Powyższy przykładowy graf opisuje relację znajomości pomiędzy osobami pewnej społeczności. W tym grafie imiona to wierzchołki grafu. Odcinki łączące dwa wierzchołki to krawędzie grafu. Krawędź łączącą wierzchołki uu i vv 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). Grafy skierowane, to takie, 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ą.

Kiedy ścieżka zaczyna się i kończy na tym samym wierzchołku, to nazywamy ją cyklem.

Czasami do krawędzi przypisane są wartości liczbowe (wagi). Na przykład na mapie drogowej. 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 mogą oznaczać odległości między miastami. Graf, którego krawędzie mają wagi nazywamy grafem ważonym.

Kiedy krawędzie są skierowane i prezentowane graficznie za pomocą strzałek, graf taki nazywamy skierowanym. 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. Jeśli wierzchołkiem początkowym krawędzi jest wierzchołek uu, a końcowym wierzchołek vv, to krawędź taką oznaczamy (u,v)(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).

Algorytm Dijkstry, a także sortowanie topologiczne przejdź - > Zasoby do pobrania (w formie pdf).