Matematyka Dyskretna

Andrzej Szepietowski

25 czerwca 2002 roku

Rozdział 1

Grafy skierowane

W tym rozdziale zajmiemy si¸e algorytmami wyszukiwania najkrótszej drogi w grafach
skierowanych. Ka˙zdej kraw¸edzi przypiszemy długo´s´c (wag¸e) i algorytmy b¸ed¸a szuka´c
drogi, dla której suma długo´sci kraw¸edzi jest najmniejsza.

1.1

Grafy skierowane

Definicja 1.1 Graf skierowany (zorientowany) to dowolna para

, ze sko´nczo-

nym zbiorem wierzchołków

i zbiorem kraw¸edzi

.

Rysunek 1.1: Graf skierowany

W grafie skierowanym kraw¸ed´z

jest skierowana od wierzchołka

do wierz-

chołka

. Wierzchołek

nazywamy pocz¸atkiem kraw¸edzi, a wierzchołek

ko ´ncem. Na

rysunkach kraw¸edzie skierowane b¸edziemy przedstawia ´c jako strzałki. Droga w grafie
skierowanym jest to ci¸ag wierzchołków

!"$#%#$#&'

, taki, ˙ze dla ka˙zdego

(

*),+

(

+.-

,

wierzchołki

/01!

,

"/

s¸a poł¸aczone kraw¸edzi¸a, czyli

2/01!" "/3546

. Drog¸e

78 !9%#$#%#$ '

nazywamy cyklem je˙zeli

":;'

, oraz wszystkie wierzchołki

8!"$#$#%#& '

s¸a ró˙zne. Na

przykład ci¸ag wierzchołków

jest cyklem w grafie z rysunku 1.1. Dla grafów

skierowanych dopuszczamy cykl zło˙zony z dwóch wierzchołków, na przykład ci¸ag

stanowi cykl w grafie z rysunku 1.1. Kraw¸ed´z typu

2< 1

, w której pocz¸atek i koniec

pokrywaj¸a si¸e, nazywamy p¸etl¸a. Mo˙zna przyj¸a´c, ˙ze p¸etla jest cyklem długo´sci jeden.

3

4

Rozdział 1. Grafy skierowane

Definicja 1.2 Graf skierowany jest (silnie) spójny, je˙zeli dla ka˙zdych dwóch jego wierz-
chołków

i

istnieje droga z

do

.

Przykład 1.3 Graf z rysunku 1.1 nie jest spójny, bo nie ma w nim drogi z

do

.

1.2

Najkrótsze drogi w grafie

Przypu´s´cmy teraz, ˙ze ka˙zdej kraw¸edzi

przypisano długo´s´c (wag¸e)

. Dopuszczamy

przy tym ujemne długo´sci. Dla ka˙zdej drogi w grafie

7%#$#$#%

zdefiniujmy jej długo´s´c jako sum¸e długo´sci kraw¸edzi, czyli

/!

2"/01!" "/3

#

Je˙zeli

, droga składa si¸e z pojedynczego punktu, to przyjmujemy, ˙ze jej długo´s´c wy-

nosi 0. W tym rozdziale interesuj¸a nas algorytmy wyznaczania najkrótszej drogi ł¸acz¸acej
dwa wierzchołki

i

w grafie.

Przykład 1.4 Jako przykład zastosowania algorytmu wyszukiwania najkrótszej drogi w
grafie rozpatrzmy sie´c poł¸acze´n, czyli graf, w którym kraw¸edzie reprezentuj¸a ł¸acza pomi¸edzy
w¸ezłami. Z ka˙zd¸a kraw¸edzi¸a

zwi¸azane jest prawdopodobie´nstwo

, ˙ze kraw¸ed´z za-

działa bez awarii. Zakładamy, ˙ze awarie poszczególnych kraw¸edzi s¸a od siebie niezale˙zne.
Przyjmijmy teraz długo´s´c kraw¸edzi

jako

. Najkrótsza droga jest wtedy

drog¸a z najmniejszym prawdopodobie´nstwem awarii.

Łatwo zauwa˙zy´c, ˙ze je˙zeli w grafie s¸a cykle o ujemnej długo´sci, to dla pewnych par

wierzchołków nie istnieje najkrótsza droga mi¸edzy nimi. Powtarzaj¸ac przej´scie wzdłu˙z
cyklu mo˙zna wtedy otrzymywa´c drogi o długo´sci dowolnie małej. Dlatego w dalszej
cz¸e´sci b¸edziemy zakłada´c, ˙ze w grafie wszystkie cykle s¸a dodatniej długo´sci.

Problem znajdowania najkrótszej drogi w grafie nieskierowanym, je˙zeli wszystkie

kraw¸edzie maj¸a dodatnie długo´sci, mo˙zna sprowadzi´c do przypadku grafu skierowane-
go. Wystarczy ka˙zd¸a kraw¸ed´z

<

zast¸api´c przez dwie kraw¸edzie

2<

i

. Je˙zeli

w grafie s¸a kraw¸edzie o ujemnych długo´sciach, to sposób ten prowadzi do powstania cykli
ujemnej długo´sci.

Opisane tu algorytmy składaj¸a si¸e z dwóch etapów. W pierwszym etapie wyznaczamy

długo´sci najkrótszych dróg z

do wszystkich wierzchołków w grafie. A dopiero w drugim

etapie wyznaczymy najkrótsz¸a drog¸e z

do

.

Najpierw opiszemy drugi etap, czyli jak znale´z´c najkrótsz¸a drog¸e z

do

, je˙zeli znane

s¸a odległo´sci z

do wszystkich wierzchołków grafu. Algorytm ten b¸edziemy opisywa ´c

przy pomocy przykładu grafu z rysunku 1.2.

Dla prostoty algorytmu przyjmujemy

2<

,

, je˙zeli

4

. Załó˙zmy, ˙ze

macierz

zawiera odległo´sci od

do wszystkich pozostałych wierzchołków grafu.

1.3. Algorytm Forda-Bellmana

5

Rysunek 1.2: Graf z długo´sciami kraw¸edzi

)

)

v

s

a

b

c

d

t

0

1

0

-1

1

2

zawiera odległo´s´c

od

, czyli długo´s´c najkrótszej drogi z

do

. Przyjmujemy

przy tym, ˙ze

oraz

, je˙zeli nie ma ˙zadnej drogi z

do

. Najkrótsz¸a

drog¸e od

do

wyznaczamy teraz od ko ´nca. Najpierw szukamy przedostatniego wierz-

chołka tej drogi, pó´zniej trzeciego od ko ´nca i tak dalej. Przedostatni wierzchołek

naj-

krótszej drogi spełnia równo´s´c

2

#

W naszym przykładzie tylko wierzchołek

spełnia t¸a równo´s´c. Zauwa˙zmy, ˙ze isnieje

droga długo´sci

z

do

. Je˙zeli przedłu˙zymy t¸e drog¸e o kraw¸ed´z

, to otrzymamy

drog¸e z

do

długo´sci

,

, czyli najkrótsz¸a drog¸e z

do

. Jest te˙z

jasne, ˙ze taki wierzchołek

istnieje. Jest to przedostatni wierzchołek dowolnej najkrótszej

drogi z

do

. Trzeci od ko ´nca wierzchołek

spełnia równo´s´c

2<

W naszym przykładzie jest to

i tak dalej, a˙z odtworzymy cał¸a drog¸e

.

Algorytm ten musi zako ´nczy´c prac¸e, poniewa˙z kolejne wierzchołki odsłanianej drogi s¸a
ró˙zne. Inaczej mieliby´smy cykl, co nie jest mo˙zliwe, je˙zeli w grafie wszystkie cykle s¸a
dodatniej długo´sci.

1.3

Algorytm Forda-Bellmana

W tym podrozdziale opiszemy pierwszy z algorytmów obliczania warto´sci macierzy

.

Mówi¸ac z grubsza polega on na przyj¸eciu najpierw pewnych górnych oszacowa ´n na war-
to´sci

i poprawianiu ich potem. Je˙zeli na jakim´s etapie pracy algorytmu mamy war-

to´s´c

, to znaczy, ˙ze znaleziono ju˙z drog¸e od

do

długo´sci

. Je˙zeli pó´zniej algo-

rytm znajdzie krótsz¸a drog¸e, to warto´s´c

zostanie poprawiona. Znajdowanie krotszej

drogi polega na szukaniu wierzchołka

spełniaj¸acego warunek

3#

6

Rozdział 1. Grafy skierowane

Algorytm [Forda-Bellmana]

Dane wej´sciowe: Graf skierowany

, długo´sci kraw¸edzi

.

Dane wyj´sciowe: Macierz

odległo´sci z

do wszystkich wierzchołków.

dla ka˙zdego

4

podstaw

;

dla ka˙zdego

-

od 1 do

zrób:

dla ka˙zdego

zrób:

dla ka˙zdego

4

zrób:

(

2<

Algorytm Forda-Bellmana najpierw podstawia

. Jest to pierwsze

przybli˙zenie. Potem w

rundach, dla ka˙zdego wierzchołka

4

algorytm sprawdza,

czy istnieje wierzchołek

, który wyznacza krótsz¸a drog¸e do

.

Przykład 1.5 Algorytm Forda-Bellmana zastosowany do grafu z rysunku 1.2 działa w
nast¸epuj¸acy sposób: Na pocz¸atku macierz

przedstawia si¸e nast¸epuj¸aco:

v

s

a

b

c

d

t

0

2

2

1

W pierwszej iteracji zewn¸etrznej p¸etli, dla

-

)

, algorytm dla ka˙zdego wierzchołka

sprawdza, czy istnieje wierzchołek

, przez który wiedzie krótsza droga do

. I

tak dla

, stwierdza,

6

)

. Oznacza, to, ˙ze

droga z

do

a potem kraw¸edzi¸a do

jest krótsza od dotychczasowego oszacowania

.

Dlatego algorytm podstawia 3 na

. Dla

warto´s´c

,

nie zmienia si¸e

poniewa˙z droga przez

)5

nie jest krótsza od dotychczasowego

oszacowania. Dla

algorytm znajduje krótsz¸a drog¸e przez

;

)

)

i zmienia

na

)

. Dla

:

warto´s´c macierzy

nie jest

korygowana, a dla

algorytm odnajduje drog¸e przez

,

5

)

i posyła

. Tak wi¸ec po pierwszej iteracji p¸etli macierz

ma nast¸epuj¸ace

warto´sci:

v

s

a

b

c

d

t

0

3

2

-1

1

4

W drugiej iteracji dla

-

tylko warto´s´c

zostaje poprawiona, gdy˙z

)

)

. Nowa warto´s´c

. Pozostałe warto´sci nie zmieniaj¸a si¸e i

po drugiej iteracji macierz

wygl¸ada tak

v

s

a

b

c

d

t

0

3

0

-1

1

4

W trzeciej iteracji p¸etli dla

-

algorytm najpierw znajduje krótsz¸a drog¸e do

(przez

)

i poprawia

)

, a potem znajduje krótsz¸a drog¸e do

(przez

) i poprawia

.

Po trzeciej iteracji macierz

wygl¸ada tak

v

s

a

b

c

d

t

0

1

0

-1

1

2

1.4. Dodatnie długo´sci, algorytm Dijsktry

7

Jest to ostateczna posta´c macierzy, gdy˙z w czwartej iteracji jej warto´sci nie s¸a ju˙z popra-
wione.

Aby udowodni´c, ˙ze algorytm działa poprawnie poka˙zemy przez indukcj¸e, ˙ze po

(

-tej ite-

racji zewn¸etrznej p¸etli

zawiera długo´s´c najkrótszej drogi z

do

zawieraj¸acej co

najwy˙zej

(

)

kraw¸edzi. Przed pierwsz¸a iteracj¸a

zawiera długo´s´c drogi zło˙zonej z

jednej lub zero kraw¸edzi. Załó˙zmy, ˙ze po

(

iteracjach

zawiera długo´s´c najkrótszej drogi

z

(

)

lub mniej kraw¸edziami.

Przypu´s´cmy, ˙ze

%#$#$#%

!

jest najkrótsz¸a spo´sród dróg z

do

z

(

lub mniej kraw¸edziami. Droga

$#%#$#$

!

jest najkrótsz¸a drog¸a do

!

z

(

)

lub mniej kraw¸edziami. Gdyby istniała krótsza droga

do

!

z co najwy˙zej

(

)

kraw¸edziami, to mieliby´smy krótsz¸a drog¸e do

z co najwy˙zej

(

kraw¸edziami; sprzeczno´s´c. Czyli długo´s´c drogi

%#$#$#$

!

jest równa

!

po

(

tej iteracji. Dlatego po

(

)

iteracji

b¸edzie zawiera´c długo´s´c najkrótszej drogi

do

z

(

kraw¸edziami.

Po zako´nczeniu pracy algorytmu

zawiera długo´s´c najkrótszej drogi z

do

,

poniewa˙z, je˙zeli w grafie wszystkie cykle s¸a dodatniej długo´sci, to w minimalnej drodze

˙zaden wierzchołek nie powtarza si¸e i droga nie zawiera wi¸ecej ni˙z

)

kraw¸edzi.

Algorytm zawiera trzy p¸etle zagnie˙zd˙zone jedna w drug¸a. Zewn¸etrzna p¸etla wykonuje

si¸e

razy. Dla ka˙zdego

-

wewn¸etrzna p¸etla wykonuje si¸e

)

razy, raz dla ka˙zdego

4

, a dla ka˙zdego

mamy

wykona ´n najbardziej wewn¸etrznej p¸etli, czyli czas

działania algorytmu mo˙zna oszacowa´c przez

$

)9

+

, gdzie

i

to

stałe. Tak wi¸ec zło˙zono´s´c czasowa algorytmu wynosi

.

1.4

Dodatnie długo´sci, algorytm Dijsktry

W tym podrozdziale podamy algorytm znajdowania odległo´sci od ´zródła do wszystkich
wierzchołków grafu dla przypadku, gdy długo´sci wszystkich kraw¸edzi s¸a dodatnie.

Algorytm Dijkstry

Dane wej´sciowe: Graf skierowany

, dodatnie długo´sci kraw¸edzi

.

Dane wyj´sciowe: Macierz

odległo´sci z

do wszystkich wierzchołków.

dla ka˙zdego

4

podstaw

;

dopóki

powtarzaj:

wybierz wierzchołek

4

taki, ˙ze

4

;

dla ka˙zdego

4

podstaw

3

2<

8

Rozdział 1. Grafy skierowane

Podobnie jak w poprzednim algorytmie na pocz¸atku macierz

zawiera długo´s´c

kraw¸edzi

1

, a je˙zeli takiej kraw¸edzi nie ma, to

. Zbiór

zawiera wierz-

chołki, dla których nie jest jeszcze wyliczona dokładna odległo´s´c od

. Poni˙zej poka˙ze-

my, ˙ze dla

4

,

zawiera długo´s´c najkrótszej spo´sród dróg, której przedostatni

wierzchołek nale˙zy do

. Nast¸epnie w ka˙zdej iteracji zewn¸etrznej p¸etli bierzemy

wierzchołek

4

, który le˙zy najbli˙zej od

. Jak si¸e za chwile oka˙ze ten wierzchołek ma

ju˙z prawidłow¸a warto´s´c

i dlatego jest on usuwany z

. Teraz korygujemy warto´sci

dla pozostałych wierzchołków z

uwzgl¸edniaj¸ac drogi, w których wierzchołek

jest przedostatni.

Przykład 1.6 Rysunek 1.3 przedstawia graf z dodatnimi długo´sciami kraw¸edzi. Poni˙z-
sza tabela ilustruje działanie algorytmu Dijkstry. Pokazuje jak w kolejnych iteracjach
zewn¸etrznej p¸etli wybrano wierzchołek

oraz jak przedstawiaj¸a si¸e zbiór

i macierz

.

iteracja

0

0

1

5

1

0

1

2

4

2

0

1

2

3

6

3

0

1

2

3

4

6

4

0

1

2

3

4

5

5

0

1

2

3

4

5

Rysunek 1.3: Graf z dodatnimi długo´sciami kraw¸edzi

)

)

)

)

)

)

Aby udowodni´c poprawno´s´c tego algorytmu, poka˙zemy przez indukcj¸e, ˙ze po ka˙zdej ite-
racji p¸etli mamy

(a) dla ka˙zdego wierzchołka

4

,

zawiera ostateczn¸a długo´s´c minimalnej

drogi z

do

.

(b) dla ka˙zdego wierzchołka

4

,

zawiera długo´s´c minimalnej spo´sród wszyst-

kich dróg z

do

, w których przedostatni wierzchołek nale˙zy do

Przed pierwsz¸a p¸etl¸a tylko

4

, a dla ka˙zdego innego wierzchołka

4

,

. Warunki (a) i (b) s¸a wi¸ec spełnione, Poniewa˙z w najkrótszej drodze do

nie ma p¸etli, wi¸ec drogi, w których

jest przedostatni składaj¸a si¸e tylko z jednej kraw¸edzi.

1.5. Najkrótsza droga w grafach acyklicznych

9

W kolejnej iteracji wybieramy wierzchołek

4

, dla którego

jest najmniejsza. Po-

ka˙zemy, ˙ze warto´s´c

jest ju˙z ostateczna, czyli jest równa długo´sci najkrótszej spo´sród

wszystkich dróg z

do

. Przypu´s´cmy, ˙ze istnieje krótsza droga i niech

b¸edzie takim

wierzchołkiem, ˙ze droga z

do

zawiera tylko wierzchołki z

i wierzchołek przed

nie nale˙zy do

. Mamy

, bo inaczej mieliby´smy sprzeczno´s´c z zało˙zeniem induk-

cyjnym, ˙ze

zawiera długo´s´c najkrótszej spo´sród dróg, z których przedostatni wierz-

chołek nie jest z

. Zauwa˙zmy, ˙ze droga z

do

ma długo´s´c równ¸a aktualnej warto´sci

. Z drugiej strony poniewa˙z długo´sci s¸a nieujemne mamy

+

sprzeczno´s´c z zasad¸a wyboru

.

Dlatego

mo˙ze by´c usuni¸ety z

. Nast¸epnie algorytm sprawdza dla ka˙zdego

4

,

czy istnieje jaka´s droga z

do

, w której wierzchołek

jest przedostani i która jest krót-

sza od aktualnej warto´sci

. Zauwa˙zmy, ˙ze dotychczasowa warto´s´c

zawierała

długo´s´c najkrótszej drogi do

, w których przedostatnim wierzchołkiem był jaki´s wierz-

chołek z

ró˙zny od

. Dlatego po tym sprawdzeniu b¸edzie spełniony warunek (b).

Czas działania algorytmu Dijkstry jest

, poniewa˙z mamy tylko podwójne za-

gnie˙zd˙zenie p¸etli i liczba iteracji obu jest ograniczona przez

.

1.5

Najkrótsza droga w grafach acyklicznych

Inny przypadek, kiedy mo˙zna szybciej ni˙z w czasie

policzy´c długo´sci najkrótszych

dróg do wszystkich wierzchołków w grafie, zachodzi wtedy, gdy w grafie nie ma cykli.
Najpierw poka˙zemy, ˙ze w grafie acyklicznym mo˙zna tak ponumerowa ´c wierzchołki tak,
ka˙zda kraw¸ed´z prowadziła od wierzchołka z ni˙zszym numerem do wierzchołka z wy˙z-
szym numerem.

Lemat 1.7 W ka˙zdym skierowanym grafie

bez cykli istnieje wierzchołek, do

którego nie wchodz¸a ˙zadne kraw¸edzie.

Dowód: We´zmy dowolny wierzchołek

!

. Je˙zeli nie wchodzi do niego, ˙zadna kraw¸ed´z,

to koniec, znale´zli´smy. Je˙zeli wchodzi, to niech

b¸edzie wierzchołkiem, z którego pro-

wadzi kraw¸ed´z do

8!

. Albo

jest dobry, albo prowadzi do niego kraw¸ed´z od jakiego´s

wierzchołka

itd. Poniewa˙z zbiór wierzchołków jest sko ´nczony i nie ma w nim cy-

klu, wi¸ec ten ci¸ag musi si¸e kiedy´s sko´nczy´c i dojdziemy do wierzchołka, do którego nie
prowadz¸a ˙zadne kraw¸edzie.

Lemat 1.8 W skierowanym grafie acyklicznym

mo˙zna tak ponumerowa´c

wierzchołki, aby ka˙zda kraw¸ed´z prowadziła od wierzchołka z ni˙zszym numerem do wierz-
chołka z wy˙zszym numerem, czyli istnieje wzajemnie jednoznaczna funkcja

)$#%#$#&

taka, ˙ze je˙zeli

2<

4

, to

21

2

.

Dowód:

10

Rozdział 1. Grafy skierowane

Jako dowód przedstawimy algorytm, który odpowiednio numeruje wierzchołki gra-

fu kolejnymi liczbami naturalnymi. Najpierw s¸a numerowane i usuwane z grafu wierz-
chołki, do których nie wchodz¸a ˙zadne kraw¸edzie. Po usuni¸eciu tych wierzchołków i
wychodz¸acych z nich kraw¸edzi znowu otrzymamy graf bez cykli, który zawiera wierz-
chołki bez wchodz¸acych kraw¸edzi. Teraz te z koleji wierzchołki s¸a numerowane kolejny-
mi numerami i usuwane z grafu, i tak dalej a˙z do ponumerowania wszystkich wierzchoł-
ków.

Rysunek 1.4: Graf acykliczny

)

)

)

)

Przykład 1.9 Zastosujmy powy˙zszy algorytm do grafu z rysunku 1.4. Wierzchołkami bez
wchodz¸acych kraw¸edzi s¸a

i

. Przypisujemy wi¸ec

)

i

oraz usuwa-

my

i

z grafu wraz z wychodz¸acymi z nich kraw¸edziami. Teraz wierzchołek

nie ma

wchodz¸acych kraw¸edzi, przypisujemy mu

i usuwamy z grafu. W dalszych kro-

kach algorytm przypisze warto´sci

,

oraz

. Ostatecznie hunkcja

ma posta´c:

v

s

a

b

c

d

t

1

4

2

3

5

6

Przedstawimy teraz algorytm wyliczaj¸acy odległo´sci z

do wszystkich wierzchołków w

grafie acyklicznym. Zakładamy przy tym, ˙ze w grafie

wierzchołki s¸a ponumerowane

tak, jak opisano to w lemacie 1.8. Bez straty ogólno´sci mo˙zna zało˙zy´c, ˙ze

jest pierwszy,

poniewa˙z nie ma ´scie˙zek z

do wierzchołków o ni˙zszych numerach.

Algorytm wyliczaj¸acy odległo´sci wszystkich wierzchołków w grafie acyklicznym

Dane wej´sciowe: acykliczny graf skierowany

;

, długo´sci kraw¸edzi

.

Dane wyj´sciowe: Macierz

odległo´sci z

do wszystkich wierzchołków.

dla ka˙zdego

4

podstaw

;

dla ka˙zdego

4

po kolei według numerów zrób:

dla ka˙zdego

,

<

2<

1.6. Zadania

11

Udowodnimy przez indukcj¸e, ˙ze po

(

-tej iteracji zewn¸etrznej p¸etli wierzchołki o nu-

merch od 1 do

(

maj¸a ju˙z prawidłowe warto´sci w macierzy

. Po pierwszej iteracji

ma prawidłow¸a warto´s´c

. W

(

tej iteracji p¸etli (zakładamy, ˙ze wierzchołki o

numerach od 1 do

(

)

maj¸a ju˙z prawidłowe warto´sci w macierzy

) obliczamy

(

.

Zauwa˙zmy, ˙ze najkrótsza droga z

do

/

przebiega przez wierzchołki o mniejszych od

(

numerach. Niech

b¸edzie przedostatnim wierzchołkiem na tej drodze. Długo´s´c tej drogi

wynosi

1

"/3

2< "/3

i zostanie odnaleziona w p¸etli.

Poniewa˙z mamy podwójne zagnie˙zd˙zenie p¸etli i w obu liczba iteracji jest ograniczona

przez

, czas działania algorytmu jest

.

Przykład 1.10 (kontynuacja przykładu 1.9) Je˙zeli zastosujemy ten algorytm do grafu z
rysunku 1.4, to w kolejnych iteracjach zewn¸etrznej p¸etli obliczy on

,

,

)

,

,

oraz

.

1.6

Zadania

1. Narysuj wszystkie grafy skierowane ze zbiorem wierzchołków

. Które

z nich s¸a spójne? Które z nich s¸a izomorficzne?

Wskazówka: Definicja izomorfizmu grafów skierowanych jest taka sama jak dla
grafów nieskierowanych.

2. Które z grafów przedstawionych na rysunkach w tym rozdziale s¸a spójne?

3. Narysuj mo˙zliwie jak najwi¸ecej nieizomorficznych grafów skierowanych z trzema

wierzchołkami

.

4. Narysuj par¸e ró˙znych i izomorficznych grafów skierowanych z mo˙zliwie najmniejsz¸a

liczb¸a wierzchołków.

Rysunek 1.5: Graf skierowany

)

)

)

)

)

5. Zastosuj algorytm Dijkstry i znajd´z najkrótsz¸a drog¸e z

do

w grafie z rysunku 1.5.

6. Zastosuj algorytm Forda-Bellmana do grafu z rysunku 1.5.

7. Znajd´z najkrótsz¸a drog¸e z

do

w grafach z rysunków 1.3 i 1.4.

8. Zastosuj algorytm Forda-Bellmana do grafów z rysunków 1.3 i 1.4.

12

Rozdział 1. Grafy skierowane

1.7

Problemy

1.7.1

Cykl Eulera w grafie skierowanym

Cykl Eulera w grafie skierowanym jest to droga zamkni˛eta przechodz ˛

aca przez ka˙zd ˛

a

kraw˛ed´z grafu dokładnie jeden raz. Udowodnij, ˙ze je˙zeli graf skierowany jest spójny jako
graf nieskierowany, to ma cykl Eulera wtedy i tylko wtedy, gdy w ka˙zdym jego wierz-
chołku liczba kraw˛edzi wchodz ˛

acych jest równa liczbie kraw˛edzi wychodz ˛

acych. Je˙zeli

w grafie jest p˛etla

, to liczymy j ˛

a jako kraw˛ed´z wchodz ˛

ac ˛

a do

i jako wychodz ˛

ac ˛

a

z

.

Zaproponuj algorytm wynajdywania cyklu Eulera w grafie skierowanym.
Które z grafów przedstawionych na rysunkach w tym rozdziale maj¸a cykle Eulera?

1.7.2

Ci ˛

ag de Bruijna

Ci ˛

ag de Bruijna rz˛edu

to cykliczne ustawienie

bitów takie, ˙ze ka˙zdy ci ˛

ag

bitów

wyst˛epuje w tym cyklu dokładnie jeden raz jako

kolejnych bitów.

Na przykład ci ˛

ag

))

jest ci ˛

agiem de Bruijna rz˛edu 2 (

)

wyst˛epuje na pozycjach 4

i 1), a ci ˛

ag

)

)))

jest ci ˛

agiem de Bruijna rz˛edu 3 (

))

wyst˛epuje na pozycjach 7, 8 i

1, a

)

na pozycjach 8, 1 i 2).

Aby otrzyma˙z ci ˛

ag de Bruijna rz˛edu

rozwa˙zmy nast˛epuj ˛

acy graf skierowany G=(V,E).

Wierzchołki grafu

%)

0

!

to zbiór wszystkich ci ˛

agów bitów długosci

:)

. Dwa

wierzchołki

,

4

tworz ˛

a kraw˛ed´z,

4

wtedy i tylko wtedy, gdy ostatnich

bitów

jest takie samo jak pierwsze

bitów

. Kraw˛ed´z ta jest etykietowana

ostatnim bitem

.

Narysuj graf

dla

,

i

.

Udowodnij, ˙ze:

Graf jest spójny (jako graf nieskierowany) i posiada cykl Eulera.

Etykiety ka˙zdej drogi długo´sci

)

tworz ˛

a nazw˛e ostatniego wierzchołka tej drogi.

Cykl Eulera ma

kraw˛edzi i przechodzi przez ka˙zdy wierzchołek dwa razy.

Etykiety cyklu Eulera tworz ˛

a ci ˛

ag de Bruijna rz˛edu

.

Wyznacz ci ˛

ag de Bruijna rz˛edu

.