ALG$7

10.1. Definicje i pojęcia podstawowe 247

Graf z rysunku 10 - 1 posiada 6 węzłów: A, B, C, D, E i F, niektóre z nich są połączone pomiędzy sobą krawędziami: (A.B), (B,C(B. D), (D.F), (D.E) i (E.F).

Węzeł C ma charakter specjalny, bowiem wychodzi z niego krawędź, która... wraca z powrotem do swojego węzła początkowego! W niektórych zagadnieniach algorytmicznych i takie dziwne „krawędzie” są potrzebne, bowiem można przy' icli pomocy modelować więcej sytuacji niż tylko z użyciem samych węzłów i krawędzi.

Numery' węzłów (lub też symboliczne etykiety literowe) służą w zasadzie tylko do rozróżniania węzłów, bez przypisywania im jednakże jakiejś określonej kolejności. Programista może jednak w razie potrzeby narzucić numerom węzłów dodatkowe znaczenie (np. w teorii gier będzie to rekord opisujący stan giy).

Z definicji pomiędzy dwoma węzłami może istnieć tylko jedna krawędź, ale możliwe jest bardzo łatwe przejście z grafu, który nie jest zgodny z naszą definicją (patrz 10-2 (a)), do grafu „standardowego” poprzez zwykłe dołożenie sztucz nych wierzchołków (rysunek 10 - 2 (b)).

Rys. 10 - 2.

„Normalizowanie " grajitf 1).

Pojęcie grafu skierowanego ma charakter najogólniejszy, gdyż graf nieskiero-wany (patrz rysunek 10-3 (a)) może być bardzo łatwo przetransformowany na skierowany (rysunek 10-3 (b)).

Rys. 10 - 3. „Normalizowanie "	a)		b)
grafu(2).	©—	-©	©

•4-

Dla pewnych zastosowań celowe jest przypisanie krawędziom grafu wartości (najczęściej liczbowych, ale mogą to również być etykiety innego typu). Zmienia nam się wówczas definicja grafu, gdyż zamiast dwójki (X, T) mamy (X, f, V). Trzeci parametr Voznacza właśnie zbiór wartości odpow iadających danym krawędziom.

W teorii grafów można napotkać jeszcze sporo innych definicji i pojęć, ale my chwilowo poprzestaniemy na tych zaprezentowanych powyżej. Nowe pojęcia, jeśli okażą się niezbędne, będą systematycznie wprowadzane w trakcie wykładu.

Obecnie przejdziemy do opisu kilku typowych metod reprezentowania grafów w pamięci komputera.