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



.