Algorytmy Grafowe

Spis treści

Wprowadzenie do Gr

Wprowadzenie do Gr

afów

afów

1 Grafy – podstawowe defin

icje

2 Graf prosty i graf ogólny

3 Elementy grafów

4 Rodzaje grafów

5 Grafy i ich reprezentacje

Algorytmy Grafowe

Algorytmy Grafowe

1 Algorytm Forda-

Bellmana

2 Algorytm Dijkstry

3 Algorytm Floyda

Wprowadzenie do

Grafów

1 Grafy – podstawowe definicje

2 Graf prosty i graf ogólny

3 Elementy grafów

4 Rodzaje grafów

5 Grafy i ich reprezentacje

Algorytmy Grafowe

1 Algorytm Forda-Bellmana

2 Algorytm Dijkstry

3 Algorytm Floyda

Grafy – podstawowe

definicje

Graf: G = (V, E)
Zbiór wierzchołków grafu:

V = {1, 2, …, n}

Zbiór krawędzi grafu:

E  { {i, j} : i ≠ j i i, jV}

Rysunek grafu:

- wierzchołek i przedstawia symbol
- krawędź {i, j} przedstawia odcinek łączący dwa

wierzchołki

Przykład grafu i jego rysunek:
G = (V, E)

V = {1, 2, 3, 4, 5, 6, 7 }
E = { {1, 2 }, {1, 3 }, {1, 4 }, {2, 3 }, {3, 4 }, {6, 7 } }

Spis treści

Graf prosty i graf ogólny

Grafem prostym, nazywamy graf G = (V, E) – (gdzie V jest

niepustym

skończonym

zbiorem

elementów

zwanych

wierzchołkami lub węzłami, a E jest skończonym zbiorem

nieuporządkowanych par różnych (w parach) elementów zbioru V

zwanym krawędziami). W każdym grafie prostym istnieje co

najwyżej jedna krawędź łącząca daną parę wierzchołków.

Jednakże wiele wyników dotyczących grafów prostych można

rozszerzyć tak, by dotyczyły obiektów ogólniejszych, w których

dwa wierzchołki mogą być połączone więcej niż jedna krawędzią.

Ponadto możemy pozbyć się ograniczenia mówiącego, że

krawędź łączy dwa różne wierzchołki i dopuścić pętle.

Spis treści

Graf prosty i graf ogólny

Powyższy obiekt, w którym mogą występować krawędzie

wielokrotne i pętle, nazywamy grafem ogólnym, lub po prostu
grafem. Zatem każdy graf prosty jest grafem ogólnym, ale nie
każdy graf ogólny jest grafem prostym. Zatem graf G składa się
z niepustego zbioru skończonego V (G), którego elementy
nazywamy wierzchołkami, i skończonej rodziny E (G) par nie
uporządkowanych (niekoniecznie różnych) elementów zbioru V
(G) nazywanych krawędziami.

Zatem na rysunku 4 zbiorem wierzchołków V (G) jest zbiór {u,

v, w, z}, a rodzina E (G) składa się z krawędzi uv, vv
(występującej dwukrotnie), vw (występującej trzykrotnie), uw
(występującej dwukrotnie) i wz.

Użycie słowa „rodzina” oznacza, że dopuszczamy istnienie

krawędzi wielokrotnych, zbioru z powtórzeniami, czyli
zbiorowości elementów z których niektóre mogą występować
wielokrotnie.

Spis treści

Elementy grafów

Spis treści

Trasą w grafie G łączącą wierzchołki x i y nazywamy ciąg x,
e1, u, e2, v…, w, ek-1, y, gdzie e1 = {x,u}, e2 = {u,v}, …,
ek-1 = {w,y} i k ≥ 1, inaczej mówiąc trasa jest to „linia” po
której przedostajemy się z jednego wierzchołka do innego,
składająca się z ciągu kolejno przechodzonych krawędzi.
Na przykład ciąg P



Q



R w grafie przedstawionym na

rysunku 5 jest trasą o długości 2, a ciąg P



S



Q



T



S



R jest trasą długości 5.

Elementy grafów

Spis treści

Drogą w grafie G= (V, E) nazywamy ciąg

wierzchołków vi



V, gdzie i = 1, …n, taki, że dla

dowolnego k = 1, …n-1, (vk, vk+1)



E, czyli taki ciąg

jego wierzchołków, że każde dwa kolejne wierzchołki
w tym ciągu są połączone trasą, gdzie wszystkie
krawędzie i wierzchołki są różne. Inaczej mówiąc
drogą nazywamy taką trasę, w której żaden
wierzchołek nie występuje więcej niż jeden raz.

Na przykład P



T



S



R jest drogą.

Elementy grafów

Spis treści

Drogą w grafie G= (V, E) nazywamy ciąg wierzchołków vi



V,

gdzie i = 1, …n, taki, że dla dowolnego k = 1, …n-1, (vk,
vk+1)



E, czyli taki ciąg jego wierzchołków, że każde dwa

kolejne wierzchołki w tym ciągu są połączone trasą, gdzie
wszystkie krawędzie i wierzchołki są różne. Inaczej mówiąc
drogą nazywamy taką trasę, w której żaden wierzchołek nie
występuje więcej niż jeden raz.

Na przykład P



T



S



R jest drogą.

Drogę v = (v1,…, vn) w grafie

G = (V, E) nazywamy

skończoną, jeśli istnieje n



N, dla którego nie ma

określonego wierzchołka vn+1, długość tą oznacza

się

v = n -1.

Drogę (lub ścieżkę) v = (v1,…, vn) w grafie G = (V,E)
nazywamy zamkniętą, jeśli v1 = vn.

Elementy grafów

Spis treści

Ścieżka i cykl
Ścieżką nazywamy trasę, w której wszystkie krawędzie
są różne, ponadto jeśli wierzchołki są różne to taka
ścieżkę nazywamy drogą. Natomiast cyklem nazywamy
ścieżkę zamkniętą zawierającą co najmniej jedną
krawędź, można zauważyć że każda pętla lub para
krawędzi wielokrotnych tworzą cykl.

Na przykład: trasa v



w



x



y



z



z



x jest

ścieżką

trasa v



w



x



y



z



x



v jest ścieżką

zamkniętą

a trasa v



w



x



v jest cyklem

Elementy grafów

Spis treści

Stopnie wierzchołków na przykładzie grafu

skierowanego.

Dla grafu G = (V, E) i jego łuku a = (i, j)



E mówimy że

wierzchołki i, j są incydentne z łukiem a tzn. że łuk a prowadzi
z wierzchołka i do j. Wierzchołki incydentne z danym łukiem
nazywamy odpowiednio jego początkiem (i) i końcem (j).

V

+

(i) – zbiór końców łuków wychodzących z wierzchołka i :

V

+

(i) = { j



V : (i, j)



E }

V

-

(i) – zbiór początków łuków wchodzących do wierzchołka i :

V

-

(i) = { j



V : (i, j)



E }

d

+

(i) = | V

+

(i) | – stopień wyjściowy wierzchołka i

d

-

(i) = | V

-

(i) | – stopień wejściowy wierzchołka i

d(i) = d

+

(i) + d

-

(i) – stopień wierzchołka i

Elementy grafów

Spis treści

Przykład wyznaczania stopni wierzchołków w grafie

V

+

(3) = {2, 4, 5}  d

+

(3) = 3; V

-

(3) = {2, 5}  d

-

(3) = 2;

d(3) = 5

V

+

(6) = {6}  d

+

(6) = 1; V

-

(6) = {6}  d

-

(6) = 1; d(6) = 2

Rodzaje grafów

Spis treści

Wśród grafów rozróżniamy następujące rodzaje:
Graf pusty – graf, którego zbiór krawędzi jest zbiorem
pustym tzn. składa się tylko z wierzchołków, oznaczany
Nn gdzie n to liczba wierzchołków

Graf pełny – graf prosty w którym dowolne dwa
wierzchołki są sąsiednie, oznaczany Kn gdzie n to liczba
wierzchołków a liczba krawędzi to n ( n - 1 ) / 2

Rodzaje grafów

Spis treści

Graf cykliczny – Graf spójny, regularny stopnia

drugiego oznaczany jako Cn gdzie n to liczba
wierzchołków.

Graf liniowy – Graf otrzymany z grafu cyklicznego

poprzez usunięcie jednej krawędzi jest oznaczany przez
Pn gdzie n to liczba wierzchołków.

Rodzaje grafów

Spis treści

Graf koło – Graf powstały z grafu cyklicznego poprzez

połączenie każdego wierzchołka z nowym, dodanym
wierzchołkiem oznaczany Wn gdzie n to liczba
wierzchołków – rys 12.

Graf planarny – to graf, który można przedstawić na

płaszczyźnie tak, by żadne dwie krawędzie się nie
przecinały – rys 13.

Rodzaje grafów

Spis treści

Graf dwudzielny – Graf jest dwudzielny jeżeli zbiór

wierzchołków grafu G można podzielić na dwa rozłączne
zbiory V

1

i V

2

w taki sposób, że każda krawędź grafu G

łączy dowolny wierzchołek ze zbioru V

1

z dowolnym

wierzchołkiem ze zbioru V

2

i jest oznaczany K

r

, s gdzie r

to ilość wierzchołków zbioru V

1

, a s to ilość

wierzchołków zbioru V

2

.

Rodzaje grafów

Spis treści

Graf regularny – każdy wierzchołek grafu ma taki sam

stopień. Jeżeli każdy wierzchołek jest stopnia r, to graf
jest regularny stopnia r i oznacza się go Kn gdzie n to
liczba wierzchołków. Szczególne znaczenie mają grafy
kubiczne, tzn. grafy regularne stopnia 3.

Rodzaje grafów

Spis treści

Graf kubiczny (w tym graf Petersena) – Graf r-

regularny jest grafem, dla którego stopień każdego
wierzchołka jest równy r. Graf 3-regularny nazywamy
grafem kubicznym, w którym wszystkie wierzchołki
mają stopień równy 3, tzn. że z każdego wierzchołka
wychodzi tyle samo krawędzi tj. 3.

Rodzaje grafów

Spis treści

Sześć postaci grafu Petersena

Rodzaje grafów

Spis treści

Rodzaje grafów

Spis treści

Graf spójny i graf niespójny – graf jest spójny wtedy i

tylko wtedy, gdy każda para wierzchołków jest
połączona drogą, w przeciwnym razie nazywamy go
grafem nie spójnym. Poniżej umieszczono przykład dla
pary wierzchołków v, w.

Grafy i ich reprezentacje

Spis treści

Graf skierowany i nieskierowany

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 (oznaczanych przez E).

Grafy dzielimy na grafy skierowane i nieskierowane:

Graf nieskierowany Graf skierowany

Grafy i ich reprezentacje

Spis treści

Graf skierowany (lub diagraf) G jest opisaną parą (V, E),

gdzie V jest zbiorem skończonym, a E jest relacją binarną
w V. Zbiór V jest nazywany zbiorem wierzchołków G, a
jego elementy są nazywane wierzchołkami. Zbiór E jest
nazywany zbiorem krawędzi G, a jego elementy
nazywamy krawędziami.

Graf skierowany

Grafy i ich reprezentacje

Spis treści

W grafie nieskierowanym G=(V, E), zbiór krawędzi E to

zbiór nieuporządkowanych par wierzchołków. Oznacza to,
iż krawędź E jest zbiorem {u, v}, gdzie, u, v



V i u



v.

W grafie nieskierowanym nie mogą występować pętle,
więc każda krawędź zawiera dokładnie dwa różne
wierzchołki.

Graf nieskierowany

Grafy i ich reprezentacje

Spis treści

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.

Graf nieskierowany

Grafy i ich reprezentacje

Spis treści

Poniżej została omówiona 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:

1

2

3

4

5

1

0

1

1

0

1

2

1

0

1

1

1

3

1

1

0

1

0

4

0

1

1

0

1

5

1

1

0

1

0

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-

(lub

górno)

-trójkątną.

Grafy i ich reprezentacje

Spis treści

Lista incydencji

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, 5

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

Grafy i ich reprezentacje

Spis treści

Lista krawędzi

Lista krawędzi jest to lista, na której przechowujemy

wszystkie krawędzie występujące w grafie.

Przykład dla grafu skierowanego

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

•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.

Grafy i ich reprezentacje

Spis treści

Macierz incydencji

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.

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

 

1

2

3

4

5

1 - 2

-1

1

0

0

0

1 - 3

1

0

-1

0

0

1 - 5

1

0

0

0

-1

2 - 4

0

-1

0

1

0

2 - 5

0

-1

0

0

1

2 - 3

0

1

-1

0

0

3 - 4

0

0

1

-1

0

5 - 4

0

0

0

1

-1

Grafy i ich reprezentacje

Spis treści

Macierz grafu jest to trochę bardziej skomplikowana
reprezentacja grafu niż poprzednie.
Należy utworzyć tablicę o rozmiarach (V+2)2. Wiersze i kolumny
numerujemy od 0 do V+1. Najpierw zajmiemy się częścią macierzy
ograniczoną przez indeksy od 1 do V. Załóżmy, że w wierszach
mamy i-te wierzchołki a w kolumnach j-te wierzchołki. Liczby,
które mogą znaleźć się na skrzyżowaniu wierzchołka i oraz j
można podzielić na 3 grupy:

od 1 do V - istnieje krawędź skierowana: i <- j

od V+1 do 2*V - istnieje krawędź skierowana: i -> j

od (-V) do (-1) - brak incydentnych krawędzi

Sedno macierzy grafu polega jednak na tym, że odczytana wartość
nie tylko informuje nas, czy istnieje krawędź łącząca wierzchołki i
oraz j, ale zawiera też adres następnego wierzchołka, który jest w
takiej samej relacji z wierzchołkiem i co wierzchołek j.

Algorytm Forda-

Bellmana

Spis treści

Algorytm

Bellmana-Forda

wyznacza

najmniejszą

odległości od ustalonego wierzchołka s do wszystkich
pozostałych w skierowanym grafie bez cykli o ujemnej
długości.

Algorytm Forda-Bellmana w każdym kroku oblicza

górne oszacowanie D(v

i

) odległości od wierzchołka s do

wszystkich pozostałych wierzchołków v

i

. W pierwszym kroku

przyjmujemy D(v

i

)=A(s,v

i

). Gdy stwierdzimy, że D(v)>D(u)

+A(u,v), to każdorazowo polepszamy aktualne oszacowanie i
podstawiamy D(v):=D(u)+A(u,v). Algorytm kończy się, gdy
żadnego oszacowania nie można już poprawić, macierz D(v

i

)

zawiera najkrótsze odległości od wierzchołka s do wszystkich
pozostałych.

Algorytm Forda-

Bellmana

Spis treści

Pseudokod wygląda następująco: (n- liczba wierzchołków)
begin;
for v:=[1..n] do D(v):=A(s,v); - przyjmujemy, że najkrótszą drogą z u do v
jest
krawędź (u,v)
for k:=1 to (n-2) do - w (n-2) krokach można zbadać każdą drogę o (n-1)
krawędziach i wybrać najkrótszą
begin
for v:=[1..n]-{s} do - odległość od s do s wynosi 0 i już się na pewno nie
zmieni
for u:=[1..n] do
D(v):=min{D(v), D(u)+A(u,v)}; - wybierz krótszą drogę
end;
Algorytm można ulepszyć sprawdzając w każdej iteracji, czy coś się
zmieniło od poprzedniej i jeśli nie, to można zakończyć obliczenia.

Algorytm Forda-

Bellmana

1

2

3

4

5

6

1

0

2

4

∞

∞

∞

2

∞

0

∞

∞

4

∞

3

∞

∞

0

-2

3

∞

4

1

∞

∞

0

∞

2

5

∞

∞

∞

∞

0

∞

6

∞

2

∞

∞

1

0

Spis treści

Dla pełnej jasności poniżej zamieszczono prosty przykład:
Oto graf i jego reprezentacja w postaci macierzy wag krawędzi.

Przyjmujemy s=1:

Przebieg obliczeń:

K

D(

1)

D(

2)

D(

3)

D(

4)

D(

5)

D(

6)

0

0

2

4

∞

∞

∞

1

0

2

4

2a

6b

4c

2

0

2

4

2

5d

4

3

0

2

4

2

5

4

Algorytm Forda-

Bellmana

Spis treści

Objaśnienia:
W pierwszym kroku (k=0) D(vi)=A(1,vi). Przepisujemy pierwszy wiersz macierzy
wag krawędzi.
a) Pierwsze skrócenie drogi:
w poprzednim kroku D(4)= ∞, gdyż nie istnieje krawędź od 1 do 4. Teraz jednak
możemy przejść przez wierzchołek 3 (odległość od 1 do 3 wynosi 4) a następnie
do 4 (waga krawędzi [3,4]=-2), długość drogi od 1 do 4 wynosi więc 4-2=2.
b) Podobnie jest tu, do wierzchołka 5 możemy dojść przez 2, 3, lub 6. Wybieramy
oczywiście drogę o mniejszej długości:
D(2)+A(2,5)=2+4=6 (ta wartość jest najmniejsza)
D(3)+A(3,5)=4+3=7
D(6)+A(6,5)= ∞+1 (ta wartość jest największa)
Wybieramy opcję z wierzchołkiem nr. 2.
c) Do wierzchołka 6 możemy dojść przez 4 (do którego dochodzimy przez 3)
droga jest więc następująca: 1, 3, 4, 6 a jej długość wynosi D(4)+A(4,6)=2+2=4
d) Jak wynika z punktu b), do wierzchołka 5 możemy dojść także poprzez
wierzchołek 6.
W poprzednim kroku poznaliśmy odległość do wierzchołka 6 i nie wynosi ona już
nieskończoność. Sprawdźmy więc, jaka byłaby długość drogi do wierzchołka 5
poprzez 6: D(6)+A(6,5)=4+1=5. Jest to wartość mniejsza niż aktualna (6), więc
znaleźliśmy krótszą drogę.
W kroku k=3 nic się nie zmieniło od kroku k=2. Kończymy obliczenia i mamy
wektor najkrótszych dróg od wierzchołka s=1 do wszystkich pozostałych.
Złożoność obliczeniowa: O(n3).

Algorytm Dijkstry

Spis treści

Algorytm Dijkstry służy do wyznaczania najmniejszej

odległości od ustalonego wierzchołka s do wszystkich
pozostałych w skierowanym grafie, jednakże graf wejściowy
nie może zawierać krawędzi o ujemnych wagach.

W

algorytmie

tym

pamiętany

jest

zbiór

Q

wierzchołków, dla których nie obliczono jeszcze najkrótszych
ścieżek, oraz wektor D[i] odległości od wierzchołka s do i.
Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor
D jest pierwszym wierszem macierzy wag krawędzi A.

Algorytm Dijkstry

Spis treści

Algorytm przebiega następująco:

•Dopóki zbiór Q nie jest pusty wykonuj:
•Pobierz ze zbioru Q wierzchołek v o najmniejszej wartości D[v] i usuń

go ze zbioru.

•Dla każdego następnika i, wierzchołka v dokonaj relaksacji ścieżki, tzn.

sprawdź, czy D[i]>D[v]+A[v,i], tzn. czy aktualne oszacowanie odległości
do wierzchołka i jest większe od oszacowania odległości do wierzchołka
v plus waga krawędzi (v,i). Jeżeli tak jest, to zaktualizuj oszacowanie D[i]
przypisując mu prawą stronę nierówności (czyli mniejszą wartość).

Jak widać z powyższego pseudokodu, algorytm wybiera z kolejki Q
"najlżejszy" wierzchołek, tzn. jest oparty na strategii zachłannej.

Wprawdzie metoda zachłanna nie zawsze daje wynik optymalny, jednak
algorytm Dijkstry jest algorytmem dokładnym.

Algorytm Dijkstry

a

b

c

d

e

a

0

10

∞

∞

5

b

∞

0

1

∞

2

c

∞

∞

0

4

∞

d

7

∞

6

0

∞

e

∞

3

9

2

0

Spis treści

Oto przykładowy graf oraz jego macierz wag krawędzi (nieskończoność oznacza brak krawędzi):

Obliczenia przebiegają następująco: (Dla S=a)
najlżejszy wierzchołek jest podkreślony, wierzchołki, dla których
wyznaczono już najkrótsze ścieżki są zaznaczone kolorem jaśniejszym

Złożoność obliczeniowa: O(n2).

Q

D(a

)

D(b

)

D(c

)

D(d

)

D(e

)

{b,c,d,

e}

0

10

∞

∞

5

{b,c,d}

0

8

14

7

5

{b,c}

0

8

13

7

5

{c}

0

8

9

7

5

{}

0

8

9

7

5

Algorytm Floyda

Spis treści

Algorytm ten służy do wyznaczania najmniejszej odległości

pomiędzy wszystkimi parami wierzchołków w skierowanym grafie bez
cykli o ujemnej długości.
Warunek nieujemności cyklu jest spowodowany faktem, że w grafie o
ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami
jest nieokreślona, ponieważ zależy od liczby przejść w cyklu.
Algorytmu tego można również użyć do obliczenia domknięcia
przechodniego relacji binarnej przedstawionej w postaci grafu
skierowanego G. Wówczas domknięcie przechodnie definiuje się jako:

En={(x,y): istnieje w G droga o niezerowej długości od x do y}

(przy tej definicji każda krawędź ma wagę 1)

Algorytm Floyda opiera się na następującym spostrzeżeniu. Niech d

ij(k)

oznacza długość najkrótszej spośród najkrótszej v

i

do v

j

o wierzchołkach

pośrednich w zbiorze {v

1

,...,v

k

}

Algorytm Floyda

Spis treści

Pseudokod wygląda następująco: (n- liczba

wierzchołków)

begin;
for i:=1 to n do
for j:=1 to n do d(i,j)=A(i,j);
for i:=1 to n do d(i,i)=0;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
d(i,j)=min( d(i,j), d(i,k)+d(k,j) );
end;

Algorytm Floyda

Spis treści

Dla przykładu graf i jego reprezentacja w postaci
macierzy wag krawędzi:

1

2

3

4

5

6

1

0

2

4

∞

∞

∞

2

∞

0

∞

∞

4

∞

3

∞

∞

0

-2

3

∞

4

1

∞

∞

0

∞

2

5

∞

∞

∞

∞

0

∞

6

∞

2

∞

∞

1

0