Mirosław Mortka
Każdy informatyk zmuszony jest do modelowania różnorodnych zjawisk wykorzystując sformalizowane struktury danych. Jedną z takich elastycznych struktur jest graf.
Definicja: Graf to niepusty zbiór wierzchołków oraz krawędzi.
(1)gdzie V – zbiór wierzchołków, E – zbiór krawędzi.
Można nim opisać choćby takie pojęcia jak sieci dróg, związki chemiczne, obwody elektryczne czy powiązania organizacyjne. W sieci dróg krawędzie to ulice, zaś wierzchołki – w zależności od założeń – to miasta bądź skrzyżowania. W związkach chemicznych atomy wyobrażone są przez wierzchołki, zaś wiązania przez krawędzie. W powiązaniach organizacyjnych zazwyczaj ludzi symbolizują wierzchołki, krawędzie to znajomości, zależności czy po prostu uczucia.
Rysunek 1. Przykłady grafów
Jednymi z ważniejszych pojęć związanych z grafami są drogi i cykle.
Droga (ścieżka) to sekwencja krawędzi – koniec jednej krawędzi jest początkiem następnej. Długość drogi to liczba krawędzi łączących poszczególnie krawędzie.
Cykl definiujemy jako drogę, która zaczyna się i kończy w tym samym wierzchołku.
Rodzaje grafów
Definicyjnie graf jest skierowany, jeśli dla krawędzi łączącej wierzchołki $v$ oraz $w$ nie zachodzi zależność $(v, w) = (w, v)$.
Graf, w którym po krawędziach można „poruszać się” tylko w jednym kierunku, nazywamy skierowanymi. Sytuację taka można przyrównać do dróg, w których poszczególne pasy jezdni przejezdne są tylko w jednym kierunku.
W grafie nieskierowanym wszystkie krawędzie traktujemy jako „dwukierunkowe jezdnie”.
Graf acykliczny – graf, który nie zawiera cykli. Przykładem takiego grafu jest drzewo.
Graf spójny – graf, w którym istnieje droga pomiędzy każdą parąwierzchołków.
Graf ważony – w przypadku, gdy każdej krawędzi przypisana jest waga. Wagami mogą być odległości pomiędzy miastami, czas przejazdu czy jego koszt. Jeżeli nie zachodzi konieczność rozróżnienia kosztu pomiędzy różnymi krawędziami mówimy o grafie bez wag.