plik

zad.1

Na początek kilka definicji:

W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków,
oznaczanych przez V) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E).

Grafy dzielimy na grafy skierowane i nieskierowane:

Rys.1. Graf nieskierowany

Rys.2. Graf skierowany

Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna.

Pętla własna to krawędź łączące wierzchołek z samym sobą.

Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi.

Istnieje kilka algorytmów do przechowania grafu w pamięci.

Omówmy najpierw macierz sąsiedztwa.

Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją
zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są
połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:

Złożoność pamięciowa: O(V2)

Widać, że macierz jest symetryczna. Stosując tablicę dynamiczną można więc zmniejszyć rozmiar
macierzy do połowy zapisując ją jako macierz dolno-(górno)-trójkątną.

Lista sąsiedztwa.

Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków
połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:

1: 2, 3, 5

2: 1, 3, 4

3: 1, 2, 4

4: 2, 3, 5

5: 4, 1

Złożoność pamięciowa: O(V+E)

Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.

Przykład dla grafu skierowanego z rys.2:

1 - 2

2 - 4

2 - 5

3 - 1

3 - 2

4 - 3

5 - 1

5 - 4

Zapisując przy pomocy tej reprezentacji graf, w którym występują krawędzie skierowane i
nieskierowane należy w przypadku krawędzi nieskierowanej z u do v zapisać krawędź
dwukrotnie: u - v oraz v - u.

Złożoność pamięciowa: O(E)

Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli
krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego
wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla
własna piszemy 2.

Oto przykład dla grafu z rys. 2.

1 - 2

-1

1 - 3

-1

1 - 5

-1

2 - 4

-1

2 - 5

-1

2 - 3

-1

3 - 4

-1

5 - 1

-1

5 - 4

-1

Złożoność pamięciowa: O(E*V)

zad.2.

Procedury przeglądania grafu w głąb (DFS) i wszerz (BFS) są bardzo często wykorzystywane w
innych, bardziej złożonych algorytmach (np. badania spójności).

W strategii DFS wybrany wierzchołek należy umieścić na stosie, zaznaczyć jako odwiedzony a
następnie przejść do jego następnika. Następnik również umieszczamy na stosie, zaznaczamy
jako odwiedzony przechodzimy do jego następnika. Jak widać procedurę można wywoływać
rekurencyjnie. Jeśli dojdziemy do takiego wierzchołka, że nie ma on krawędzi incydentych z
nieodwiedzonymi wierzchołkami, należy usunąć go ze stosu i pobrać ze stosu kolejny
wierzchołek do przeszukania. W praktyce stosuje się zasadę, że jeśli przeszukiwany wierzchołek
jest połączony krawędziami z wieloma wierzchołkami, wybiera się do przeszukania wierzchołek o
najmniejszej liczbie porządkowej. Dlatego szukając kolejny nieodwiedzony następnik należy
rozpoczynać od końca macierzy. Przeszukiwanie DFS wykorzystuje się do badania spójności
grafu. Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich
wierzchołków grafu to graf jest spójny.

Aby przeszukać graf wszerz (BFS) należy zamiast stosu wykorzystać kolejkę do przechowywania
wierzchołków a kolejnych nieodwiedzonych następników szukać od początku macierzy.

Oto przykładowy graf:

PRZYKŁAD:

Przeszukiwanie w głąb (DFS):

Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy na stos wszystkie jego następniki, w
kolejności od tego z największym indeksem:

Odwiedzone: 1; Stos: 3, 2;

Bierzemy wierzchołek ze stosu, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone

jeszcze następniki na stos:

Odwiedzone: 1, 2; Stos: 3, 5, 4;

Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:

Odwiedzone: 1, 2, 4; Stos: 3, 5;

Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:

Odwiedzone: 1, 2, 4, 5; Stos: 3;

Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 3 jest 6, ten wierzchołek
jeszcze nie jest odwiedzony więc wrzucamy go na stos:

Odwiedzone: 1, 2, 4, 5, 3; Stos: 6;

Bierzemy wierzchołek ze stosu, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma
czego wrzucić na stos:

Odwiedzone: 1, 2, 4, 5, 3, 6; Stos: ;

Stos jest pusty zatem zakończyliśmy przeszukiwanie grafu w głąb.

Przeszukiwanie w szerz (BFS):

Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy do kolejki wszystkie jego następniki, w
kolejności od tego z najmniejszym indeksem:

Odwiedzone: 1; Kolejka: 2, 3;

Bierzemy wierzchołek z kolejki, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone
jeszcze następniki do kolejki:

Odwiedzone: 1, 2; Kolejka: 3, 4, 5;

Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 3 jest 6 więc wrzucamy
go do kolejki:

Odwiedzone: 1, 2, 3; Kolejka: 4, 5, 6;

Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:

Odwiedzone: 1, 2, 3, 4; Kolejka: 5, 6;

Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:

Odwiedzone: 1, 2, 3, 4, 5; Kolejka: 6;

Bierzemy wierzchołek z kolejki, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma
czego wrzucić do kolejki:

Odwiedzone: 1, 2, 3, 4, 5, 6; Kolejka: ;

Kolejka jest pusta zatem zakończyliśmy przeszukiwanie grafu w szerz.

zad.3.

Jeśli graf jest zadany macierzą incydencji, to każdy wiersz tej macierzy reprezentuje w grafie
jeden wierzchołek o numerze równym numerowi wiersza (wiersz 0 → wierzchołek 0, wiersz 1 →
wierzchołek 1, itd.). Kolejne elementy wiersza związane są z kolejnymi krawędziami w grafie
(kolumna 0 → krawędź 0, kolumna 1 → krawędź 1, itd.). Jeśli graf jest grafem skierowanym, to j-
ty element i-tego wiersza może przyjąć tylko jedną z trzech wartości:

0 : j-ta krawędź nie zawiera 1 - j-ta krawędź wychodzi -1 - j-ta krawędź wchodzi

i-tego wierzchołka

z i-tego wierzchołka do j-tego wierzchołka

Stopień wejściowy to liczba krawędzi wchodzących do wierzchołka. Liczymy go obliczając ilość
elementów wiersza równych -1. Podobnie stopień wyjściowy to liczba krawędzi wychodzących z
wierzchołka, którą znajdziemy obliczając ilość elementów równych 1. W tym celu tworzymy dwa
liczniki:

lkwy - licznik krawędzi wyjściowych

lkwe - licznik krawędzi wejściowych

Przeglądamy kolejne wiersze macierzy incydencji. Najpierw zerujemy oba liczniki, następnie
przeglądamy kolejne elementy wiersza. Jeśli natrafimy na element równy 1, to zwiększamy
licznik lkwy. Jeśli natrafimy na element równy -1, zwiększamy lkwe. Po przeglądnięciu całego
wiersza wypisujemy numer wiersza (czyli numer wierzchołka grafu) oraz kolejno stan liczników
lkwe i lkwy. Tak postępujemy z każdym wierszem macierzy.

zad.4

Jednym z podstawowych problemów w teorii grafów jest znajdowanie połączeń
pomiędzy dwoma wybranymi wierzchołkami. Ścieżką (ang. path) nazywamy
uporządkowany zbiór wierzchołków, które musimy kolejno przejść, aby dotrzeć w grafie
od jednego wybranego wierzchołka do innego wybranego wierzchołka. Ścieżek takich
może być kilka (lub może nie istnieć żadna - wtedy wierzchołki nazywamy
izolowanymi).

Od wierzchołka

do wierzchołka

można dojść wieloma różnymi
ścieżkami:
ścieżka nr 1:

- 2 -

ścieżka nr 2:

- 4 - 5 -

ścieżka nr 3:

- 4 - 5 - 2 -

ścieżka nr 4:

- 4 - 2 -

Jeśli z krawędziami grafu związane są wagi, to każda ze ścieżek posiada swój koszt
przejścia równy sumie wag krawędzi łączących poszczególne wierzchołki ścieżki. Dla
podanego wyżej grafu ścieżki od wierzchołka 1 do 3 mają następujący koszt:
ścieżka nr 1 - koszt = 3 + 3 = 6
ścieżka nr 2 - koszt = 3 + 1 + 1 = 5
ścieżka nr 3 - koszt = 3 + 1 + 5 + 3 = 12
ścieżka nr 4 - koszt = 3 + 6 + 3 = 12

Przez najkrótszą ścieżkę (ang. the shortest path) łączącą w grafie dwa wybrane
wierzchołki będziemy rozumieli ścieżkę o najmniejszym koszcie przejścia.

Od wierzchołka

do wierzchołka

najkrótszą ścieżką jest

ścieżka nr 1: 1 - 2 - 3

ścieżka nr 2:

- 4 - 5 -

ścieżka nr 3: 1 - 4 - 5 - 2 - 3
ścieżka nr 4: 1 - 4 - 2 - 3

o koszcie przejścia równym 5.

Gdyby przykładowy graf był grafem nieskierowanym, to najkrótszą ścieżką byłaby
ścieżka 1 - 3 o koszcie 2.
Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym
wierzchołkiem a wszystkimi pozostałymi. Dodatkowo wylicza również koszt przejścia
każdej z tych ścieżek. Bardzo ważnym założeniem w algorytmie Dijkstry są nieujemne
wagi krawędzi. Jeśli krawędzie mogą przyjmować wagi ujemne, to

NIE WOLNO

stosować algorytmu Dijkstry (zobacz na algorytm

Bellmana-Forda

zad.5

Drzewo rozpinające (ang. spanning tree) grafu jest jego podgrafem-drzewem, które zawiera

wszystkie wierzchołki grafu. Dany graf może posiadać wiele różnych drzew rozpinających.

Drzewo rozpinające w szerz (ang. BFST - Breadth First Spanning Tree) powstaje w trakcie

przechodzenia przez graf za pomocą algorytmu BFS. Jeśli wierzchołkiem startowym będzie
najwyższy wierzchołek grafu.

Najpierw tworzymy krawędzie pierwszego poziomu do wszystkich wierzchołków (fioletowych)
połączonych krawędzią z wierzchołkiem startowym (krawędzie niebieskie). Następnie

przechodzimy przez kolejne wierzchołki drugiego poziomu (fioletowe) łącząc je krawędziami
fioletowymi ze wszystkimi sąsiadującymi wierzchołkami (zielonymi), które jeszcze nie zostały

umieszczone w drzewie rozpinającym. Dla tego konkretnego grafu wierzchołki zielone są już
liśćmi drzewa rozpinającego i nie tworzą w nim dalszych krawędzi.

Algorytm tworzenia drzewa rozpinającego w szerz

przykład:

w głąb