Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
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!" "/3 546
. Drog¸e
7 8 !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
.