Pojecie Grafu

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)
\begin{equation} G = (V, E) \end{equation}

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.

mapka.gif grupa.gif
chem.gif
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.

skierowany.gif

W grafie nieskierowanym wszystkie krawędzie traktujemy jako „dwukierunkowe jezdnie”.

nieskierowany.gif

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License