8

Podstawowe algorytmy teorii

grafów

8.1. Najkrótsze ±cie»ki

Je»eli kraw¦dziom grafu zostaªy przyporz¡dkowane pewne liczby (wagi kraw¦dzi), to graf

z tak¡, dodatkowo okre±lon¡ na zbiorze kraw¦dzi, funkcj¡ nazywa¢ b¦dziemy grafem z wa-

gami. Przez dªugo±¢ ±cie»ki w takim grae b¦dziemy wówczas rozumieli sum¦ wag jej

kraw¦dzi. W grafach, w których nie okre±lono wag na kraw¦dziach (lub wszystkie wagi

s¡ równe) przez dªugo±¢ ±cie»ki rozumiemy, tak jak dotychczas, liczb¦ jej kraw¦dzi. Znaj-

dowanie najkrótszej ±cie»ki mi¦dzy dwoma ustalonymi wierzchoªkami s i t grafu bez wag

(z jednakowymi wagami) mo»emy oczywi±cie realizowa¢ za pomoc¡ przeszukiwania grafu

wszerz (BFS).

8.2. Drzewa minimalne  algorytm Kruskala

Generowanie drzewa rozpi¦tego danego grafu spójnego G na n wierzchoªkach mo»na re-

alizowa¢ bior¡c kolejno kraw¦dzie z pewnej listy i akceptuj¡c je po sprawdzeniu, czy nie

tworz¡ one cyklu z dotychczas zaakceptowanymi kraw¦dziami. Zauwa»my, »e do czasu

kiedy zaakceptowanych kraw¦dzi b¦dzie n − 1, czyli do czasu otrzymania drzewa, roz-

pi¦ty podgraf grafu G generowany zbiorem zaakceptowanych kraw¦dzi jest lasem. Je»eli

w ka»dym drzewie takiego lasu wyró»nimy jeden wierzchoªek  korze«  a kraw¦dzie

drzewa zamienimy ªukami tak, by z korzenia do dowolnego innego wierzchoªka drzewa

mo»na byªo przej±¢ po ±cie»ce skierowanej (zauwa»my, »e wybór korzenia jednoznacznie

takie skierowanie okre±la), to las ten mo»emy okre±li¢ przypisuj¡c ka»demu wierzchoª-

kowi v dwie etykiety (r(v), p(v)), gdzie: r(v) oznacza korze« drzewa (etykieta Korze«), do

którego nale»y v, natomiast p(v) jest bezpo±rednim poprzednikiem wierzchoªka v w tym

drzewie (etykieta Poprzednik). Je»eli kolejn¡ kraw¦dzi¡ z listy jest: e = (v

i

, v

j

)

, dla której

r

(v

i

) = r(v

j

)

, to v

i

i v

j

s¡ w tym samym drzewie i kraw¦d¹ e zamyka cykl  odrzucamy

j¡. Zaakceptowana kraw¦d¹ ª¡czy natomiast dwa drzewa lasu w jedno i nale»y przepro-

wadzi¢ zmian¦ etykiet. Mo»emy przyj¡¢, »e otrzymane drzewo b¦dzie miaªo jako korze«

mniejszy z korzeni poª¡czonych drzew.

Je»eli mamy do czynienia z grafem z wagami, to najcz¦±ciej interesuje nas znalezienie

rozpi¦tego drzewa o minimalnej wadze, to znaczy drzewa z najmniejsz¡ sum¡ wag jego

kraw¦dzi. Aby znale¹¢ drzewo o »¡danych wªasno±ciach mo»emy zastosowa¢ algorytm

Kruskala (algorytm zachªanny). Innym algorytmem rozwi¡zuj¡cym ten problem jest

algorytm Prima znany pod nazw¡ algorytmu najbli»szego s¡siada.

14

8. Podstawowe algorytmy teorii grafów

Omówimy algorytm Kruskala. Polega on na tym, »e w ka»dym kroku wybieramy

w grae G = (V, E) now¡ kraw¦d¹ o najmniejszej wadze (je±li jest ich kilka to wybie-

ramy dowoln¡ z nich). Je»eli kraw¦d¹ nie zamyka »adnego cyklu, to dodajemy j¡ do lasu,

w przeciwnym razie odrzucamy. Kraw¦d¹ t¦ usuwamy równie» z grafu G. Proces konty-

nuujemy do momentu, a» wybierzemy |V | − 1 kraw¦dzi, które utworz¡ rozpi¦te drzewo

grafu. Do szybkiego rozpoznawania, czy kraw¦d¹ zamyka cykl mo»emy wykorzysta¢ tech-

nik¦ etykietowania wierzchoªków etykietami Korze«.

Niech graf G = (V, E) b¦dzie dany macierz¡ wag. Zaªó»my, »e graf G jest spójny.

Algorytm Kruskala.

1. Wybierz kraw¦d¹, która nie jest p¦tl¡, e

1

tak, by waga tej kraw¦dzi byªa najmniejsza.

2. Je»eli kraw¦dzie e

1

, e

2

, . . . , e

k

zostaªy ju» wybrane, to z pozostaªych E\{e

1

, e

2

, . . . , e

k

}

wybierz kraw¦d¹ e

k

+1

w taki sposób aby speªnione byªy dwa warunki:

•

graf, który skªada si¦ tylko z kraw¦dzi e

1

, e

2

, . . . , e

k

, e

k

+1

byª acykliczny (mo-

»emy tu zastosowa¢ etykietowanie zwi¡zane z korzeniami drzew budowanego

lasu);

•

waga kraw¦dzi e

k

+1

byªa najmniejsza.

3. Je±li zakceptowanych zostaªo |V | − 1 kraw¦dzi, to STOP.

Twierdzenie 8.1. Drzewo rozpi¦te skonstruowane za pomoc¡ algorytmu Kruskala jest

optymalne.

Przykªad 8.1. Korzystaj¡c z algorytmu Kruskala znale¹¢ optymalne drzewo rozpi¦te dla

grafu o macierzy wag:

W

=











∞

1

∞ 10

8

3

1

∞ 13 10

6

4

∞ 13 ∞ 15 ∞ 11
10 10 15 ∞

9

∞

8

6

∞

9

∞

7

3

4

11 ∞

7

∞











8.3. Obchody Eulera

Przykªad 8.2. Które z nast¦puj¡cych gur mog¡ by¢ narysowane bez odrywania kredy od

tablicy, rysuj¡c ka»d¡ lini¦ tylko jeden raz ?

8.3. Obchody Eulera

15

Szlak, który zawiera ka»d¡ kraw¦d¹ grafu G nazywamy szlakiem Eulera grafu G.

Obchód grafu G to sko«czony, domkni¦ty spacer przechodz¡cy przez ka»d¡ kraw¦d¹ G

przynajmniej jeden raz.

Obchód Eulera jest obchodem zawieraj¡cym ka»d¡ kraw¦d¹ grafu G dokªadnie jeden raz

(jest to po prostu domkni¦ty szlak Eulera).

Graf nazywamy eulerowskim (grafem Eulera) je»eli zawiera obchód Eulera.

Graf nazywamy póªeulerowskim je»eli zawiera szlak Eulera.

Twierdzenie 8.2. Niepusty spójny graf jest eulerowski wtedy i tylko wtedy, gdy nie po-

siada wierzchoªków o nieparzystym stopniu.
Wniosek 8.3. Graf spójny ma szlak Eulera wtedy i tylko wtedy, gdy ma co najwy»ej dwa

wierzchoªki stopnia nieparzystego.

Przykªad 8.3. Poka», »e je»eli w G nie ma wierzchoªka nieparzystego stopnia, to istniej¡

kraw¦dziowo rozª¡czne cykle C

1

, C

2

, . . . , C

m

takie, »e

E

(G) = E(C

1

) ∪ E(C

2

) ∪ · · · ∪ E(C

m

) .

8.3.1 Problem chi«skiego listonosza

Listonosz odbiera przesyªki z poczty, dostarcza je a nast¦pnie wraca na poczt¦. Musi

oczywi±cie przej±¢ przez ka»d¡ ulic¦ w swoim rejonie przynajmniej raz. Ze wzgl¦du na

ten warunek pragnie wybra¢ obchód w taki sposób by jak najmniej spacerowa¢. Powy»-

szy problem znany jest jako problem chi«skiego listonosza", od chi«skiego matematyka

Kuana, który go rozpatrywaª (1962). W grae z wagami deniujemy wag¦ obchodu

v

0

e

1

, v

1

e

2

, . . . , e

n

v

0

jako P

n
i

=1

w

(e

i

)

. Oczywi±cie, problem chi«skiego listonosza sprowadza si¦ do znalezienia

obchodu o minimalnej wadze w spójnym grae o nieujemnych wagach. Je»eli G jest eule-

rowski, to obchód Eulera jest optymalny, poniewa» jest obchodem przechodz¡cym przez

ka»d¡ kraw¦d¹ dokªadnie jeden raz. Problem chi«skiego listonosza ma wówczas proste roz-

wi¡zanie, poniewa» istnieje prosty algorytm znajdowania obchodu Eulera w eulerowskim

grae.

Algorytm Fleury'ego

1. Wybierz dowolny wierzchoªek v

0

i podstaw W

0

= v

0

2. Przypu±¢my, »e szlak W

i

= v

0

e

1

v

1

e

2

. . . e

i

v

i

zostaª wybrany. Wybierz kraw¦d¹ e

i

+1

nale»¡c¡ do E − {e

1

, e

2

, . . . , e

i

}

tak, by

• e

i

+1

byªa incydentna z v

i

• e

i

+1

nie byªa kraw¦dzi¡ ci¦cia grafu G

i

= G − {e

1

, . . . , e

i

}

chyba, »e nie ma

innej alternatywy

3. STOP je»eli krok 2 nie mo»e by¢ wykonany.

Wprowad¹my operacj¦ duplikowania kraw¦dzi. O kraw¦dzi e, o wadze w(e), mówimy, »e

zostaªa zduplikowana, je»eli jej ko«ce poª¡czyli±my now¡ kraw¦dzi¡ o wadze w(e). Mo»emy

przeformuªowa¢ problem chi«skiego listonosza w nast¦puj¡cy sposób: dany jest graf G

o nieujemnych wagach na kraw¦dziach:

16

8. Podstawowe algorytmy teorii grafów

1. Znale¹¢ za pomoc¡ duplikowania kraw¦dzi eulerowski wa»ony nadgraf G

∗

grafu G

taki, »e

X

e∈E

(G

∗

)−E(G)

w

(e)

jest najmniejsza z mo»liwych

2. Znale¹¢ obchód Eulera w G

∗

.

8.4. Grafy Hamiltona

Denicja 8.1 (‘cie»ka i cykl Hamiltona). ‘cie»ka zawieraj¡ca ka»dy wierzchoªek
v

∈ V (G)

jest nazywana ±cie»k¡ Hamiltona grafu G, podobnie, cykl Hamiltona jest to cykl,

który zawiera wszystkie wierzchoªki grafu G (cykl rozpi¦ty).

Denicja 8.2 (Graf Hamiltona). Graf, który zawiera cykl Hamiltona nazywa si¦ grafem

Hamiltona (grafem hamiltonowskim).

W przeciwie«stwie do grafów eulerowskich nie istnieje prosty warunek konieczny i do-

stateczny na to, aby graf byª hamiltonowski. Mo»na jednak poda¢ szereg warunków ko-

niecznych i osobno wystarczaj¡cych na istnienie tego cyklu.

Twierdzenie 8.4. Je»eli graf G jest hamiltonowski, to dla ka»dego niepustego podzbioru
S

zbioru wierzchoªków V (G) zachodzi

ω

(G − S) 6 |S|.

Powy»sze twierdzenie mo»e sªu»y¢ nam do pokazania, »e dany graf nie jest hamiltonow-

ski. Jednak»e ta metoda nie zawsze mo»e by¢ zastosowana (nie jest to bowiem warunek

dostateczny). Nie pomo»e nam ona, na przykªad, w przypadku grafu Petersena (patrz

Rysunek 8.1).

Rysunek 8.1: Graf Petersena.

8.5. Problem w¦druj¡cego komiwoja»era

Podró»uj¡cy komiwoja»er pragnie zªo»y¢ wizyt¦ w pewnych miastach i zaªó»my, »e chce

on powróci¢ do punktu startowego. Maj¡c dany czas podró»y (koszt podró»y) pomi¦dzy

miastami, jak powinien uªo»y¢ plan podró»y aby wizytowa¢ miasta dokªadnie raz i aby ta

podró» byªa najkrótsza (najta«sza). W terminologii grafowej oznacza to szukanie cyklu

(±cie»ki) hamiltonowskiego o minimalnej wadze w wa»onym grae peªnym.