Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Grafy skierowane
W tym rozdziale zajmiemy się algorytmami wyszukiwania najkrótszej drogi w grafach
skierowanych. Każdej krawędzi przypiszemy długość (wagę) i algorytmy będą szukać
drogi, dla której suma długości krawędzi jest najmniejsza.
Najpierw podamy podstawowe definicje i fakty, część z nich była już przedstawiona
w rozdziale pierwszym.
1.1 Grafy skierowane
Definicja 1.1 Graf skierowany (zorientowany) to dowolna para G = (V, E), ze skończo-
nym zbiorem wierzchoÅ‚ków V i zbiorem krawÄ™dzi E Ä…" V × V .
Rysunek 1.1: Graf skierowany
a c
b
e
d
W grafie skierowanym krawędz
e = (u, v) jest skierowana od wierzchołka u do wierz-
chołka v. Wierzchołek u nazywamy początkiem krawędzi, a wierzchołek v końcem. Na
rysunkach krawędzie skierowane będziemy przedstawiać jako strzałki. Droga w grafie
skierowanym jest to ciąg wierzchołków v0, v1, . . . , vk, taki, że dla każdego i, 1 d" i d" k,
wierzchołki vi-1, vi są połączone krawędzią, czyli (vi-1, vi) " E. Drogę v0, v1, . . . , vk
nazywamy cyklem jeżeli v0 = vk, oraz wszystkie wierzchołki v1, . . . , vk są różne. Na
przykład ciąg wierzchołków a, b, e, d, a jest cyklem w grafie z rysunku 1.1. Dla grafów
3
4 Rozdział 1. Grafy skierowane
skierowanych dopuszczamy cykl złożony z dwóch wierzchołków, na przykład ciąg a, d, a
stanowi cykl w grafie z rysunku 1.1. Krawędz
typu (u, u), w której początek i koniec
pokrywają się, nazywamy pętlą. Można przyjąć, że pętla jest cyklem długości jeden.
Definicja 1.2 Graf skierowany jest (silnie) spójny, jeżeli dla każdych dwóch jego wierz-
chołków u i v istnieje droga z u do v.
Przykład 1.3 Graf z rysunku 1.1 nie jest spójny, bo nie ma w nim drogi z c do b.
1.2 Najkrótsze drogi w grafie
Przypuśćmy teraz, że każdej krawędzi e przypisano długość (wagę) w(e). Dopuszczamy
przy tym ujemne długości. Dla prostoty algorytmu przyjmujemy w(u, v) = ", jeżeli
(u, v) " E. Dla każdej drogi w grafie
/
v0, . . . , vp
zdefiniujmy jej długość jako sumę długości krawędzi, czyli
p
w(vi-1, vi).
i=1
Jeżeli p = 0, droga składa się z pojedynczego punktu, to przyjmujemy, że jej długość wy-
nosi 0. W tym rozdziale interesują nas algorytmy wyznaczania najkrótszej drogi łączącej
dwa wierzchołki s i t w grafie.
Przykład 1.4 Jako przykład zastosowania algorytmu wyszukiwania najkrótszej drogi w
grafie rozpatrzmy sieć połączeń, czyli graf, w którym krawędzie reprezentują łącza pomię-
dzy węzłami. Z każdą krawędzią e związane jest prawdopodobieństwo p(e), że krawędz

zadziała bez awarii. Zakładamy, że awarie poszczególnych krawędzi są od siebie nieza-
leżne. Przyjmijmy teraz długość krawędzi e jako w(e) = - log p(e). Najkrótsza droga
jest wtedy drogą z najmniejszym prawdopodobieństwem awarii.
A
atwo zauważyć, że jeżeli w grafie są cykle o ujemnej długości, to dla pewnych par
wierzchołków nie istnieje najkrótsza droga między nimi. Powtarzając przejście wzdłuż
cyklu można wtedy otrzymywać drogi o długości dowolnie małej. Dlatego w dalszej czę-
ści będziemy zakładać, że w grafie wszystkie cykle są dodatniej długości.
Problem znajdowania najkrótszej drogi w grafie nieskierowanym, jeżeli wszystkie
krawędzie mają dodatnie długości, można sprowadzić do przypadku grafu skierowane-
go. Wystarczy każdą krawędz
{u, v} zastąpić przez dwie krawędzie (u, v) i (v, u). Jeżeli
w grafie są krawędzie o ujemnych długościach, to sposób ten prowadzi do powstania cykli
ujemnej długości.
Większość znanych algorytmów wyszukiwania najkrótszej drogi działa według nastę-
pujÄ…cego schematu:
Algorytm wyszukiwania najkrótszej drogi od wierzchołka s do t
Etap I: Wyznacz długości najkrótszych dróg z s do wszystkich wierzchołków w grafie.
Etap II: Wytycz najkrótszą drogę z s do t.
1.3. II etap 5
1.3 II etap
Najpierw opiszemy, na przykładzie grafu z rysunku 1.2, jak znalez
ć najkrótszą drogę z s
do t, jeżeli znane są odległości z s do wszystkich wierzchołków grafu.
Rysunek 1.2: Graf z długościami krawędzi
2 1
s a
b
1
1
2
2 2 1
c
d t
-2 4
Niech macierz D zawiera odległości od s do wszystkich pozostałych wierzchołków
grafu.
v s a b c d t
D[v] 0 1 0 -1 1 2
D[v] zawiera odległość v od s, czyli długość najkrótszej drogi z s do v. Przyjmujemy przy
tym, że D[s] = 0 oraz D[v] = ", jeżeli nie ma żadnej drogi z s do v. Najkrótszą drogę
od s do t wyznaczamy teraz od końca. Najpierw szukamy przedostatniego wierzchołka
tej drogi, póz
niej trzeciego od końca i tak dalej. Przedostatni wierzchołek v najkrótszej
drogi spełnia równość
D[t] = D[v] + w(v, t).
W naszym przykładzie tylko wierzchołek v = a spełnia tą równość. Zauważmy, że isnieje
droga długości D[v] z s do v. Jeżeli przedłużymy tę drogę o krawędz
(v, t), to otrzymamy
drogę z s do t długości D[v] + w(v, t) = D[t], czyli najkrótszą drogę z s do t. Jest też
jasne, że taki wierzchołek v istnieje. Jest to przedostatni wierzchołek dowolnej najkrótszej
drogi z s do t. Trzeci od końca wierzchołek u spełnia równość
D[v] = D[u] + w(u, v)
W naszym przykładzie jest to u = b i tak dalej, aż odtworzymy całą drogę s, d, c, b, a, t.
Algorytm ten musi zakończyć pracę, ponieważ kolejne wierzchołki odsłanianej drogi są
różne. Inaczej mielibyśmy cykl, co nie jest możliwe, jeżeli w grafie wszystkie cykle są
dodatniej długości.
1.4 Algorytm Forda-Bellmana
W tym i następnych podrozdziałach zajmiemy się I etapem, czyli obliczaniem wartości
macierzy odległości D. Mówiąc z grubsza algorytmy wyliczające D przyjmują na począt-
ku pewne górne oszacowania na wartości D[v] i poprawiają je potem. Poprawa wartości
D[v] następuje wtedy, gdy algorytm znajdzie krótszą drogę z s do v.
6 Rozdział 1. Grafy skierowane
Algorytm [Forda-Bellmana]
Dane wejściowe: Graf skierowany G = (V, E), długości krawędzi w : E R.
Dane wyjściowe: Macierz D odległości z s do wszystkich wierzchołków.
Dla każdego v " V podstaw D[v] := w(s, v)
D[s] := 0;
Dla każdego k od 1 do n - 2 zrób:
dla każdego v = s zrób.

dla każdego u " V zrób:
D[v] := min(D[v], D[u] + w(u, v))
Algorytm Forda-Bellmana najpierw podstawia D[v] := w(s, v). Jest to pierwsze
przybliżenie. Potem w n-2 rundach, dla każdego wierzchołka v " V algorytm sprawdza,
czy istnieje wierzchołek u, który wyznacza krótszą drogę do v.
Przykład 1.5 Algorytm Forda-Bellmana zastosowany do grafu z rysunku 1.2 działa w
następujący sposób: Na początku macierz D przedstawia się następująco:
v s a b c d t
D[v] 0 " 2 2 1 "
W pierwszej iteracji zewnętrznej pętli, dla k = 1, algorytm dla każdego wierzchołka
v = s sprawdza, czy istnieje wierzchołek u, przez który wiedzie krótsza droga do v. I

tak dla v = a, stwierdza, D[b] + w(b, a) = 2 + 1 < " = D[a]. Oznacza, to, że
droga z s do b a potem krawędzią do a jest krótsza od dotychczasowego oszacowania ".
Dlatego algorytm podstawia 3 na D[a]. Dla v = b wartość D[b] = 2 nie zmienia się
ponieważ droga przez c D[c] + w(c, b) = 2 + 1 = 3 nie jest krótsza od dotychczasowego
oszacowania. Dla v = c algorytm znajduje krótszą drogę przez d; D[d] + w(d, c) =
1 + (-2) = -1 < D[c] i zmienia D[c] na -1. Dla v = d wartość macierzy D nie jest
korygowana, a dla v = t algorytm odnajduje drogÄ™ przez a, D[a] + w(a, t) = 3 + 1 =
4 < " i posyła D[t] := 4. Tak więc po pierwszej iteracji pętli macierz D ma następujące
wartości:
v s a b c d t
D[v] 0 3 2 -1 1 4
W drugiej iteracji dla k = 2 tylko wartość D[b] zostaje poprawiona, gdyż D[c]+w(c, b) =
-1 + 1 = 0 < 2 = D[b]. Nowa wartość D[b] = 0. Pozostałe wartości nie zmieniają się i
po drugiej iteracji macierz D wyglÄ…da tak
v s a b c d t
D[v] 0 3 0 -1 1 4
W trzeciej iteracji pętli dla k = 3 algorytm najpierw znajduje krótszą drogę do a (przez b)
i poprawia D[a] := 1, a potem znajduje krótszą drogę do t (przez a) i poprawia D[t] := 2.
Po trzeciej iteracji macierz D wyglÄ…da tak
1.5. Dodatnie długości, algorytm Dijsktry 7
v s a b c d t
D[v] 0 1 0 -1 1 2
Jest to ostateczna postać macierzy, gdyż w czwartej iteracji jej wartości nie są już popra-
wione.
Aby udowodnić, że algorytm działa poprawnie pokażemy przez indukcję, że po i-tej ite-
racji zewnętrznej pętli D[v] zawiera długość najkrótszej drogi z s do v zawierającej co
najwyżej i + 1 krawędzi. Przed pierwszą iteracją D[v] zawiera długość drogi złożonej z
jednej lub zero krawędzi. Załóżmy, że po i iteracjach D zawiera długość najkrótszej drogi
z i + 1 lub mniej krawędziami.
Przypuśćmy, że
s = v0, . . . , vr+1, vr+2 = v
jest najkrótszą spośród dróg z s do v z i+2 lub mniej krawędziami. Droga s = v0, . . . , vr+1
jest najkrótszą drogą do vr+1 z i+1 lub mniej krawędziami. Gdyby istniała krótsza droga
do vr+1 z co najwyżej i+1 krawędziami, to mielibyśmy krótszą drogę do v z co najwyżej
i+2 krawędziami; sprzeczność. Czyli długość drogi s = v0, . . . , vr+1 jest równa D[vr+1]
po i tej iteracji. Dlatego po i + 1 iteracji D[v] będzie zawierać długość najkrótszej drogi
do v z i + 2 krawędziami.
Po zakończeniu pracy algorytmu D[v] zawiera długość najkrótszej drogi z s do v,
ponieważ, jeżeli w grafie wszystkie cykle są dodatniej długości, to w minimalnej drodze
żaden wierzchołek nie powtarza się i droga nie zawiera więcej niż n - 1 krawędzi.
Algorytm zawiera trzy pętle zagnieżdżone jedna w drugą. Zewnętrzna pętla wykonuje
się n - 2 razy. Dla każdego k wewnętrzna pętla wykonuje się n - 1 razy, raz dla każdego
v " V - {s}, a dla każdego v mamy n wykonań najbardziej wewnętrznej pętli, czyli czas
dziaÅ‚ania algorytmu można oszacować przez c · (n - 2)(n - 1)n d" c n3, gdzie c i c to
stałe. Tak więc złożoność czasowa algorytmu wynosi O(n3).
1.5 Dodatnie długości, algorytm Dijsktry
W tym podrozdziale podamy algorytm znajdowania odległości od z
ródła do wszystkich
wierzchołków grafu dla przypadku, gdy długości wszystkich krawędzi są dodatnie.
Algorytm Dijkstry
Dane wejściowe: Graf skierowany G = (V, E), dodatnie długości krawędzi w : E
R+.
Dane wyjściowe: Macierz D odległości z s do wszystkich wierzchołków.
dla każdego v " V podstaw D[v] := w(s, v)
D[s] := 0;
T := V - {s}
dopóki T = " powtarzaj:

wybierz wierzchołek u " T taki, że D[u] = min{D[p] | p " T }
T := T - {u};
dla każdego v " T
podstaw D[v] := min(D[v], D[u] + w(u, v))
8 Rozdział 1. Grafy skierowane
Podobnie jak w poprzednim algorytmie na początku macierz D[u] zawiera długość
krawędzi (s, u), a jeżeli takiej krawędzi nie ma, to D[u] = ". W czasie wykonywania
algorytmu zbiór T zawiera wierzchołki, dla których nie jest jeszcze wyliczona dokładna
odległość od s, a ponadto dla każdego v " T , D[v] zawiera długość najkrótszej spośród
dróg, której przedostatni wierzchołek należy do V - T . W każdej iteracji zewnętrznej
pętli bierzemy wierzchołek u " T , który leży najbliżej od s. Jak się za chwile okaże
ten wierzchołek ma już prawidłową wartość D[u] i dlatego jest on usuwany z T . Teraz
korygujemy wartości D[v] dla pozostałych wierzchołków z T uwzględniając drogi, w
których wierzchołek u jest przedostatni.
Przykład 1.6 Rysunek 1.3 przedstawia graf z dodatnimi długościami krawędzi. Poniż-
sza tabela ilustruje działanie algorytmu Dijkstry. Pokazuje jak w kolejnych iteracjach
zewnętrznej pętli wybrano wierzchołek u oraz jak przedstawiają się zbiór T i macierz D.
iteracja u T D[s] D[a] D[b] D[c] D[d] D[t]
0 {a, b, c, d, t} 0 1 " 5 " "
1 a {b, c, d, t} 0 1 2 4 " "
2 b {c, d, t} 0 1 2 3 " 6
3 c {d, t} 0 1 2 3 4 6
4 d {t} 0 1 2 3 4 5
5 t " 0 1 2 3 4 5
Rysunek 1.3: Graf z dodatnimi długościami krawędzi
1 1
s a
b
1 4
3 1
5
c
d t
1 1
Aby udowodnić poprawność tego algorytmu, pokażemy przez indukcję, że po każdej ite-
racji pętli mamy
(a) dla każdego wierzchołka v " V - T , D[v] zawiera ostateczną długość minimalnej
drogi z s do v.
(b) dla każdego wierzchołka v " T , D[v] zawiera długość minimalnej spośród wszyst-
kich dróg z s do v, w których przedostatni wierzchołek należy do V - T
Przed pierwszą pętlą tylko s " V - T , a dla każdego innego wierzchołka v " T ,
D[v] = w(s, v). Warunki (a) i (b) są więc spełnione, Ponieważ w najkrótszej drodze do v
nie ma pętli, więc drogi, w których s jest przedostatni składają się tylko z jednej krawę-
dzi. W kolejnej iteracji wybieramy wierzchołek u " T , dla którego D[u] jest najmniejsza.
1.6. Najkrótsza droga w grafach acyklicznych 9
Pokażemy, że wartość D[u] jest już ostateczna, czyli jest równa długości najkrótszej spo-
śród wszystkich dróg z s do u. Przypuśćmy, że istnieje krótsza droga i niech y będzie
takim wierzchołkiem, że droga z y do u zawiera tylko wierzchołki z T i wierzchołek
przed y nie należy do T . Mamy y = u, bo inaczej mielibyśmy sprzeczność z założeniem

indukcyjnym, że D[u] zawiera długość najkrótszej spośród dróg, z których przedostat-
ni wierzchołek nie jest z T . Zauważmy, że droga z s do y ma długość równą aktualnej
wartości D[y]. Z drugiej strony ponieważ długości są nieujemne mamy
D[y] = d(s, y) d" d(s, u) < D[u]
sprzeczność z zasadą wyboru u.
Dlatego u może być usunięty z T . Następnie algorytm sprawdza dla każdego v " T ,
czy istnieje jakaś droga z s do v, w której wierzchołek u jest przedostani i która jest krót-
sza od aktualnej wartości D[u]. Zauważmy, że dotychczasowa wartość D[v] zawierała
długość najkrótszej drogi do v, w których przedostatnim wierzchołkiem był jakiś wierz-
chołek z V - T różny od u. Dlatego po tym sprawdzeniu będzie spełniony warunek (b).
Czas działania algorytmu Dijkstry jest O(n2), ponieważ mamy tylko podwójne za-
gnieżdżenie pętli i liczba iteracji obu jest ograniczona przez n.
1.6 Najkrótsza droga w grafach acyklicznych
Inny przypadek, kiedy można szybciej niż w czasie O(n3) policzyć długości najkrótszych
dróg do wszystkich wierzchołków w grafie, zachodzi wtedy, gdy w grafie nie ma cykli.
Najpierw pokażemy, że w grafie acyklicznym można tak ponumerować wierzchołki, żeby
każda krawędz
prowadziła od wierzchołka z niższym numerem do wierzchołka z wyż-
szym numerem.
Lemat 1.7 W każdym skierowanym grafie G = (V, E) bez cykli istnieje wierzchołek, do
którego nie wchodzą żadne krawędzie.
Dowód: Wez
my dowolny wierzchołek v1. Jeżeli nie wchodzi do niego, żadna krawędz
,
to koniec, znalez
liśmy. Jeżeli wchodzi, to niech v2 będzie wierzchołkiem, z którego pro-
wadzi krawędz
do v1. Albo v2 jest dobry, albo prowadzi do niego krawędz
od jakiegoÅ›
wierzchołka v3 itd. Ponieważ zbiór wierzchołków jest skończony i nie ma w nim cyklu,
więc ten ciąg musi się kiedyś skończyć i dojdziemy do wierzchołka, do którego nie pro-
wadzą żadne krawędzie.
Lemat 1.8 W skierowanym grafie acyklicznym G = (V, E) można tak ponumerować
wierzchołki, aby każda krawędz
prowadziła od wierzchołka z niższym numerem do wierz-
chołka z wyższym numerem, czyli istnieje wzajemnie jednoznaczna funkcja h : V
{1, . . . , |V |} taka, że jeżeli (u, v) " E, to h(u) < h(v).
Dowód:
Jako dowód przedstawimy algorytm, który odpowiednio numeruje wierzchołki grafu
kolejnymi liczbami naturalnymi. Najpierw są numerowane i usuwane z grafu wierzchołki,
10 Rozdział 1. Grafy skierowane
do których nie wchodzą żadne krawędzie. Po usunięciu tych wierzchołków i wychodzą-
cych z nich krawędzi znowu otrzymamy graf bez cykli, który zawiera wierzchołki bez
wchodzących krawędzi. Teraz te z koleji wierzchołki są numerowane kolejnymi numera-
mi i usuwane z grafu, i tak dalej aż do ponumerowania wszystkich wierzchołków.
Rysunek 1.4: Graf acykliczny
2 1
s a
b
-3
1
-2
1 2
c
d t
3 1
Przykład 1.9 Zastosujmy powyższy algorytm do grafu z rysunku 1.4. Wierzchołkami bez
wchodzących krawędzi są s i b. Przypisujemy więc h(s) = 1 i h(b) = 2 oraz usuwamy s
i b z grafu wraz z wychodzącymi z nich krawędziami. Teraz wierzchołek c nie ma wcho-
dzących krawędzi, przypisujemy mu h(c) = 3 i usuwamy z grafu. W dalszych krokach
algorytm przypisze wartości h(a) = 4, h(d) = 5 oraz h(t) = 6. Ostatecznie funkcja h
ma postać:
v s a b c d t
h[v] 1 4 2 3 5 6
Przedstawimy teraz algorytm wyliczający odległości z s do wszystkich wierzchołków w
grafie acyklicznym. Zakładamy przy tym, że w grafie G wierzchołki są ponumerowane
tak, jak opisano to w lemacie 1.8. Bez straty ogólności można założyć, że s jest pierwszy,
ponieważ nie ma ścieżek z s do wierzchołków o niższych numerach.
Algorytm wyliczający odległości wszystkich wierzchołków w grafie acyklicznym
Dane wejściowe: acykliczny graf skierowany G = (V, E), długości krawędzi w : E
R.
Dane wyjściowe: Macierz D odległości z s do wszystkich wierzchołków.
Dla każdego v " V podstaw D[v] := "
D[s] := 0;
dla każdego v " V po kolei według numerów zrób:
dla każdego u < v,
D[v] := min(D[v], D[u] + w(u, v))
Udowodnimy przez indukcję, że po i-tej iteracji zewnętrznej pętli wierzchołki o nu-
merch od 1 do i mają już prawidłowe wartości w macierzy D. Po pierwszej iteracji s
ma prawidłową wartość D[s] = 0. W i tej iteracji pętli (zakładamy, że wierzchołki o
numerach od 1 do i - 1 mają już prawidłowe wartości w macierzy D) obliczamy D[i].
1.7. Zadania 11
Zauważmy, że najkrótsza droga z s do vi przebiega przez wierzchołki o mniejszych od i
numerach. Niech u będzie przedostatnim wierzchołkiem na tej drodze. Długość tej drogi
wynosi d(s, u) + w(u, vi) = D[u] + w(u, vi) i zostanie odnaleziona w pętli.
Ponieważ mamy podwójne zagnieżdżenie pętli i w obu liczba iteracji jest ograniczona
przez n, czas działania algorytmu jest O(n2).
Przykład 1.10 (kontynuacja przykładu 1.9) Jeżeli zastosujemy ten algorytm do grafu z
rysunku 1.4, to w kolejnych iteracjach zewnętrznej pętli obliczy on D[s] = 0, D[b] = ",
D[c] = 1, D[a] = -2, D[d] = -4 oraz D[t] = -3.
1.7 Zadania
1. Narysuj wszystkie grafy skierowane ze zbiorem wierzchołków V = {a, b}. Które
z nich są spójne? Które z nich są 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ą spójne?
3. Narysuj możliwie jak najwięcej nieizomorficznych grafów skierowanych z trzema
wierzchołkami {a, b, c}.
4. Narysuj parę różnych i izomorficznych grafów skierowanych z możliwie najmniej-
szą liczbą wierzchołków.
Rysunek 1.5: Graf skierowany
1 1
s a
b
4
1
1
6 3 1
c
t d
1 4
5. Zastosuj algorytm Dijkstry i znajdz
najkrótszą drogę z s do t w grafie z rysunku 1.5.
6. Zastosuj algorytm Forda-Bellmana do grafu z rysunku 1.5.
7. Znajdz
najkrótszą drogę z s do t 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.8 Problemy
1.8.1 Spójność
Powiemy, że graf skierowany G = (V, E) jest słabo spójny, jeżeli dla każdej pary wierz-
chołków u, v " V , albo istnieje ścieżka z u do v, albo ścieżka z v do u. Podaj przykład
grafu, który jest słabo spójny, ale nie jest (silnie) spójny.
Powiemy, że graf skierowany G = (V, E) jest spójny jako graf nieskierowany, jeżeli
jest on spójny po zignorowaniu zwrotów krawędzi. Dokładniej, dla G konstruujemy graf
nieskierowny GN = (VN , EN ), z takim samym zbiorem wierzchołków VN = V , oraz
zbiorem krawędzi EN składającym się z tych par {u, v}, dla których u = v oraz w G

istnieje krawędz
(u, v) lub (v, u). Podaj przykład grafu skierowanego, który jest spójny
jako graf nieskierowany, ale nie jest słabo spójny.
1.8.2 Cykl Eulera w grafie skierowanym
Cykl Eulera w grafie skierowanym jest to droga zamknięta przechodząca przez każdą
krawędz
grafu dokładnie jeden raz. Udowodnij, że jeżeli graf skierowany jest spójny jako
graf nieskierowany, to ma cykl Eulera wtedy i tylko wtedy, gdy w każdym jego wierz-
chołku liczba krawędzi wchodzących jest równa liczbie krawędzi wychodzących. Jeżeli
w grafie jest pętla (u, u), to liczymy ją podwojnie: jako krawędz
wchodzÄ…cÄ… do u i jako
wychodzÄ…cÄ… z u. Zaproponuj algorytm wynajdywania cyklu Eulera w grafie skierowa-
nym. Które z grafów przedstawionych na rysunkach w tym rozdziale mają cykle Eulera?
1.8.3 CiÄ…g de Bruijna
Ciąg de Bruijna rzędu n to cykliczne ustawienie 2n bitów takie, że każdy ciąg n bitów
występuje w tym cyklu dokładnie jeden raz jako n kolejnych bitów. Na przykład ciąg
0011 jest ciągiem de Bruijna rzędu 2 (10 występuje na pozycjach 4 i 1), a ciąg 00010111
jest ciągiem de Bruijna rzędu 3 (110 występuje na pozycjach 7, 8 i 1, a 100 na pozycjach
8, 1 i 2). Aby otrzymaż ciąg de Bruijna rzędu n rozważmy następujący graf skierowany
G=(V,E). Wierzchołki grafu V = {0, 1}n-1 to zbiór wszystkich ciągów bitów długosci
n - 1. Dwa wierzchołki u, v " V tworzą krawędz
, (u, v) " E wtedy i tylko wtedy,
gdy ostatnich n - 2 bitów u jest takie samo jak pierwsze n - 2 bitów v. Krawędz
ta jest
etykietowana ostatnim bitem v.
Narysuj graf G dla n = 2, 3 i 4. Wyznacz ciąg de Bruijna rzędu 4. Udowodnij, że:
" Graf G jest spójny (jako graf nieskierowany) i posiada cykl Eulera.
" Etykiety każdej drogi długości n-1 tworzą nazwę ostatniego wierzchołka tej drogi.
" Cykl Eulera ma 2n krawędzi i przechodzi przez każdy wierzchołek dwa razy.
" Etykiety cyklu Eulera tworzą ciąg de Bruijna rzędu n.