ALG$6

246 Rozdział 10. Elementy algorytmiki gratów

Ta historyczna anegdota stanowi jednocześnie doskonały przykład na to, do czego grafy mogą się w praktyce przydać: wszelkie zadania algorytmiczne, w których w grę wchodzą problemy odnajdywania (optymalnych) dróg, mogą być przez grały doskonale modelowane. Oczywiście nie tylko one!

Programista, który dobrze pozna i zrozumie możliwości związane z użyciem grafów, praktycznie podwaja swoje kompetencje związane z umiejętnością sprawnego modelowania problemów do rozwiązania Dość paradoksalną stroną wielu zagadnień programistycznych jest to, że potrafią one rozwiązywać się niemalże „same" pod warunkiem dobrego zmodelowania całości.

Następny paragraf będzie poświęcony podstawowemu słownictwu związanemu z grafami, po czym przejdziemy do sposobów reprezentowania ich w programach komputerowych.

10.1.Definicje i pojęcia podstawowe

Niezbyt duże grafy doskonale dają się przedstawiać w postaci wiele mówiących rysunków, takich jak np. 10 - 1.

Rys. W - 1.

Przykład grafu

Grafem G nazywamy parę (X, O, gdzie X oznacza zbiór tzw. węzłów (albo wierzchołków), a T zbiór (x,y) e X' jest zespołem krawędzi.

Graf jest skierowany, jeśli krawędziom został przypisany jakiś kierunek (na rysunkach symbolizowany przez strzałkę).

Jeśli weźmiemy pod uwagę dwa węzły grafu. x i y. połączone krawędzią, to węzeł ,v jest węzłem początkowym, a węzeł y węzłem końcowym.