Md10

Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Grafy skierowane
W tym rozdziale zajmiemy sie algorytmami wyszukiwania najkrótszej drogi w grafach
�
skierowanych. Każdej kraw� przypiszemy długość (wage) i algorytmy beda szukać
edzi � � �
drogi, dla której suma długości kraw� jest najmniejsza.
edzi
1.1 Grafy skierowane

Definicja 1.1 Graf skierowany (zorientowany) to dowolna para , ze skończo-

nym zbiorem wierzchołków i zbiorem kraw� .
edzi
Rysunek 1.1: Graf skierowany

W grafie skierowanym kraw� jest skierowana od wierzchołka do wierz-
edz

chołka . Wierzchołek nazywamy poczatkiem kraw� a wierzchołek końcem. Na
� edzi,
rysunkach kraw� skierowane bedziemy przedstawiać jako strzałki. Droga w grafie
edzie �

skierowanym jest to ciag wierzchołków , taki, że dla każdego ,
�

wierzchołki , sa połaczone kraw� � czyli . Droge
� � edzia, �

nazywamy cyklem jeżeli , oraz wszystkie wierzchołki sa różne. Na
�

przykład ciag wierzchołków jest cyklem w grafie z rysunku 1.1. Dla grafów
�

skierowanych dopuszczamy cykl złożony z dwóch wierzchołków, na przykład ciag
�

stanowi cykl w grafie z rysunku 1.1. Kraw� typu , w której poczatek i koniec
edz �
pokrywaja sie, nazywamy petla. Można przyjać, że petla jest cyklem długości jeden.
� � � � � �
3
4 Rozdział 1. Grafy skierowane
Definicja 1.2 Graf skierowany jest (silnie) spójny, jeżeli dla każdych 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śćmy teraz, że każdej kraw� przypisano długość (wage) . Dopuszczamy
edzi �
przy tym ujemne długości. Dla każdej drogi w grafie

zdefiniujmy jej długość jako sum� długości kraw� czyli
e edzi,

Jeżeli , droga składa sie z pojedynczego punktu, to przyjmujemy, że jej długość wy-
�
nosi 0. W tym rozdziale interesuja nas algorytmy wyznaczania najkrótszej drogi łaczacej
� � �
dwa wierzchołki i w grafie.
Przykład 1.4 Jako przykład zastosowania algorytmu wyszukiwania najkrótszej drogi w
grafie rozpatrzmy sieć połaczeń, czyli graf, w którym kraw� reprezentuja łacza pomiedzy
� edzie � � �

w� Z każda kraw� � zwiazane jest prawdopodobieństwo , że kraw� za-
ezłami. � edzia � edz
działa bez awarii. Zakładamy, że awarie poszczególnych kraw� sa od siebie niezależne.
edzi �

Przyjmijmy teraz długość kraw� jako . Najkrótsza droga jest wtedy
edzi
droga z najmniejszym prawdopodobieństwem awarii.
�
Aatwo zauważyć, że jeżeli w grafie sa cykle o ujemnej długości, to dla pewnych par
�
wierzchołków nie istnieje najkrótsza droga miedzy nimi. Powtarzajac przejście wzdłuż
� �
cyklu można wtedy otrzymywać drogi o długości dowolnie małej. Dlatego w dalszej
cześci bedziemy zakładać, że w grafie wszystkie cykle sa dodatniej długości.
� � �
Problem znajdowania najkrótszej drogi w grafie nieskierowanym, jeżeli wszystkie
kraw� maja dodatnie długo można sprowadzić do przypadku skierowane-
edzie � ści, grafu

go. Wystarczy każda kraw� zastapić przez dwie kraw�
� edz � edzie i . Jeżeli
w grafie sa kraw� o ujemnych długościach, to sposób ten prowadzi do powstania cykli
� edzie
ujemnej długości.
Opisane tu algorytmy składaja sie z dwóch etapów. W pierwszym etapie wyznaczamy
� �
długości najkrótszych dróg z do wszystkich wierzchołków w grafie. A dopiero w drugim
etapie wyznaczymy najkrótsza droge z do .
� �
Najpierw opiszemy drugi etap, czyli jak znalezć najkrótsza droge z do , jeżeli znane
� �
sa odległości z do wszystkich wierzchołków grafu. Algorytm ten bedziemy opisywać
� �
przy pomocy przykładu grafu z rysunku 1.2.

Dla prostoty algorytmu przyjmujemy , jeżeli . Załóżmy, że
macierz zawiera odległości od do wszystkich pozostałych wierzchołków grafu.
1.3. Algorytm Forda-Bellmana 5
Rysunek 1.2: Graf z długościami kraw�
edzi

v s a b c d t

0 1 0 -1 1 2

,
zawiera odległość od czyli długość najkrótszej drogi z do . Przyjmujemy

przy tym, że oraz , jeżeli nie ma żadnej drogi z do . Najkrótsza
�
droge od do wyznaczamy teraz od końca. Najpierw szukamy przedostatniego wierz-
�

chołka tej drogi, pózniej trzeciego od końca i tak dalej. Przedostatni wierzchołek naj-
krótszej drogi spełnia równość

W naszym przykładzie tylko wierzchołek spełnia ta równość. Zauważmy, że isnieje
�

przedłużymy � � edz
droga długości z do . Jeżeli te droge o kraw� , to otrzymamy

droge z do długości , czyli najkrótsza droge z do . Jest też
� � �

jasne, że taki wierzchołek istnieje. Jest to przedostatni wierzchołek dowolnej najkrótszej

drogi z do . Trzeci od końca wierzchołek spełnia równość

W naszym przykładzie jest to i tak dalej, aż odtworzymy cała droge .
� �
Algorytm ten musi zakończyć prace, ponieważ kolejne wierzchołki odsłanianej drogi sa
� �
różne. Inaczej mielibyśmy cykl, co nie jest możliwe, jeżeli w grafie wszystkie cykle sa
�
dodatniej długości.
1.3 Algorytm Forda-Bellmana
W tym podrozdziale opiszemy pierwszy z algorytmów obliczania wartości macierzy .
Mówiac grubsza polega on na przyjeciu najpierw pewnych górnych oszacowań na war-
� z �

tości i poprawianiu ich potem. Jeżeli na jakimś etapie pracy algorytmu mamy war-

tość , to znaczy, że znaleziono już drog od do długości . Jeżeli pózniej algo-
e
�

rytm znajdzie krótsza droge, to wartość zostanie poprawiona. Znajdowanie krotszej
� �

drogi polega na szukaniu wierzchołka spełniajacego warunek
�

6 Rozdział 1. Grafy skierowane
Algorytm [Forda-Bellmana]

Dane wejściowe: Graf skierowany , długości kraw� .
edzi
Dane wyjściowe: Macierz odległości z do wszystkich wierzchołków.

dla każdego podstaw

;

dla każdego od 1 do zrób:

dla każdego zrób:

dla każdego zrób:

Algorytm Forda-Bellmana najpierw podstawia . Jest to pierwsze

przybliżenie. Potem w rundach, dla każdego wierzchołka algorytm sprawdza,

czy istnieje wierzchołek , który wyznacza krótsza droge do .
� �
Przykład 1.5 Algorytm Forda-Bellmana zastosowany do grafu z rysunku 1.2 działa w
nastepujacy sposób: Na poczatku macierz przedstawia sie nastepujaco:
� � � � � �
v s a b c d t

0 2 2 1

W pierwszej iteracji zewnetrznej petli, dla , algorytm dla każdego wierzchołka
� �

,
sprawdza, czy istnieje wierzchołek przez który wiedzie krótsza droga do . I

tak dla , stwierdza, . Oznacza, to,
że

droga z do a potem kraw� � do jest krótsza od dotychczasowego oszacowania .
edzia

Dlatego algorytm podstawia na . Dla wartość nie zmienia sie
3 �

ponieważ droga przez nie jest krótsza od dotychczasowego

oszacowania. Dla algorytm znajduje krótsza e przez ;
� drog �

ść
i zmienia na . Dla warto macierzy nie jest

korygowana, a dla algorytm odnajduje droge przez ,
�

� � � �
i posyła . Tak wiec po pierwszej iteracji petli macierz ma nastepujace
wartości:
v s a b c d t

0 3 2 -1 1 4

W drugiej iteracji tylko wartość zostaje poprawiona, gdyż
dla

� �
. Nowa wartość . Pozostałe wartości nie zmieniaja sie i
po drugiej iteracji macierz wyglada tak
�
v s a b c d t

0 3 0 -1 1 4

W trzeciej iteracji dla algorytm najpierw znajduje krótsza droge do (przez )
petli � �
�

i poprawia , a potem znajduje krótsza droge do (przez ) i poprawia .
� �
Po trzeciej iteracji macierz wyglada tak
�
v s a b c d t

0 1 0 -1 1 2
1.4. Dodatnie długości, algorytm Dijsktry 7
Jest to ostateczna postać macierzy, gdyż w czwartej iteracji jej wartości nie sa już popra-
�
wione.
Aby udowodnić, że algorytm działa poprawnie pokażemy przez indukcje, że po -tej ite-
�

racji zewnetrznej petli zawiera długość najkrótszej drogi z do zawierajacej co
� � �

najwyżej kraw� Przed pierwsza iteracja zawiera długość drogi złożonej z
edzi. � �
jednej lub zero kraw� Załóżmy, że po iteracjach zawiera długość najkrótszej drogi
edzi.

z lub mniej kraw�
edziami.
Przypuśćmy, że

jest najkrótsza spośród dróg z do z lub mniej kraw� Droga
� edziami.

jest � droga do z lub mniej kraw� Gdyby istniała krótsza droga
najkrótsza � edziami.

do z co najwyżej kraw� to mielibyśmy krótsza drog e do z co najwyżej
edziami, � �

kraw� sprzecznoś długoś drogi jest równa
edziami; ć. Czyli ć

po tej iteracji. Dlatego po iteracji bedzie zawierać długość najkrótszej drogi
�

do z kraw�
edziami.

Po zakończeniu pracy algorytmu zawiera długość najkrótszej drogi z do ,

ponieważ, jeżeli w grafie wszystkie cykle sa dodatniej długości, to w minimalnej drodze
�

żaden wierzchołek nie powtarza sie i droga nie zawiera wiecej niż kraw�
� � edzi.
Algorytm zawiera trzy petle zagnieżdżone jedna w druga. Zewnetrzna petla wykonuje
� � � �

sie razy. Dla każdego wewnetrzna petla wykonuje sie razy, raz dla każdego
� � � �

, a dla każdego mamy wykonań najbardziej � � czyli czas
wewnetrznej petli,

działania algorytmu można oszacować przez , gdzie i to

stałe. Tak wiec złożoność czasowa algorytmu wynosi .
�
1.4 Dodatnie długości, algorytm Dijsktry
W tym podrozdziale podamy algorytm znajdowania odległości od zródła do wszystkich
wierzchołków grafu dla przypadku, gdy długości wszystkich kraw� sa dodatnie.
edzi �
Algorytm Dijkstry

Dane wejściowe: Graf skierowany , dodatnie długości kraw�
edzi

.
Dane wyjściowe: Macierz odległości z do wszystkich wierzchołków.

dla każdego podstaw

;

dopóki powtarzaj:

wybierz wierzchołek taki, że

;

dla każdego podstaw

8 Rozdział 1. Grafy skierowane

Podobnie jak w poprzednim algorytmie na poczatku macierz zawiera długość
�

kraw� , a jeżeli takiej kraw� nie ma, to . Zbiór zawiera wierz-
edzi edzi
chołki, dla których nie jest jeszcze wyliczona dokładna odległość od . Poniżej pokaże-

my, że dla , zawiera długość najkrótszej spośród dróg, której przedostatni

wierzchołek należy do . Nastepnie w każdej iteracji zewnetrznej petli bierzemy
� � �

wierzchołek , który le najbliżej od . Jak sie za chwile okaże ten wierzchołek ma
ży �

już a
prawidłow� wartość i dlatego jest on usuwany z . Teraz korygujemy wartości

� �
dla pozostałych wierzchołków z uwzgledniajac drogi, w których wierzchołek
jest przedostatni.
Przykład 1.6 Rysunek 1.3 przedstawia graf z dodatnimi długościami kraw� Poniż-
edzi.
sza tabela ilustruje działanie algorytmu Dijkstry. Pokazuje jak w kolejnych iteracjach

zewnetrznej petli wybrano wierzchołek oraz jak przedstawiaja sie 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ściami kraw�
edzi

Aby udowodnić poprawność tego algorytmu, pokażemy przez indukcje, że po każdej ite-
�
racji petli mamy
�

(a) dla każdego wierzchołka , zawiera ostateczna długość minimalnej
�

drogi z do .

(b) dla każdego wierzchołka , zawiera długość minimalnej śród wszyst-
spo

kich dróg z do , w których przedostatni wierzchołek należy do

Przed pierwsza petla tylko , a dla każdego innego wierzchołka ,
� � �

� �
. Warunki (a) i (b) sa wiec spełnione, Ponieważ w najkrótszej drodze do
nie ma petli, wiec drogi, w których jest przedostatni składaja sie tylko z jednej kraw�
� � � � edzi.
1.5. Najkrótsza droga w grafach acyklicznych 9

W kolejnej iteracji wybieramy wierzchołek , dla którego jest najmniejsza. Po-

każemy, że wartość jest już ostateczna, czyli jest równa długości najkrótszej spośród

wszystkich dróg z do . Przypuśćmy, że istnieje krótsza droga i niech bedzie takim
�

wierzchołkiem, że droga z zawiera tylko wierzchołki z i wierzchołek przed
do

nie należy do . Mamy , bo inaczej mielibyśmy sprzeczność z założeniem induk-

cyjnym, że zawiera długość najkrótszej spośród dróg, z których przedostatni wierz-

chołek nie jest z . Zauważmy, że droga z do ma długość równa aktualnej wartości
�

�
. Z drugiej strony ponieważ długości sa nieujemne mamy

sprzeczność zasada wyboru .
z �

Dlatego może być usuniety z . Nastepnie algorytm sprawdza dla każdego ,
� �

czy istnieje jakaś droga z do , w której wierzchołek jest przedostani i która jest krót-

sza od aktualnej wartości . Zauważmy, że dotychczasowa wartość zawierała

długość najkrótszej drogi do , w których przedostatnim wierzchołkiem był jakiś wierz-

chołek z różny od . Dlatego po tym bedzie spełniony warunek (b).
sprawdzeniu �
Czas działania algorytmu Dijkstry jest , ponieważ mamy tylko podwójne za-
gnieżdżenie petli i liczba iteracji obu jest ograniczona przez .
�
1.5 Najkrótsza droga w grafach acyklicznych

Inny przypadek, kiedy można szybciej niż w czasie 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 tak,
każda kraw� prowadziła od wierzchołka z niższym numerem do wierzchołka z wyż-
edz
szym numerem.

Lemat 1.7 W każdym skierowanym grafie bez cykli istnieje wierzchołek, do
którego nie wchodza żadne kraw�
� edzie.

Dowód: Wezmy dowolny wierzchołek . Jeżeli nie wchodzi do niego, żadna kraw�
edz,

to koniec, znalezliśmy. Jeżeli wchodzi, to niech bedzie wierzchołkiem, z którego pro-
�

wadzi kraw� do . Albo jest dobry, albo prowadzi do niego kraw� od jakiegoś
edz edz

wierzchołka itd. Ponieważ zbiór wierzchołków jest skończony i nie ma w nim cy-
klu, wiec ten ciag musi sie kiedyś skończyć i dojdziemy do wierzchołka, do którego nie
� � �
prowadza żadne kraw�
� edzie.

Lemat 1.8 W skierowanym grafie acyklicznym można tak ponumerować
wierzchołki, aby każda kraw� prowadziła od wierzchołka z niższym numerem do wierz-
edz

chołka z numerem, czyli wzajemnie jednoznaczna funkcja
wyższym istnieje

taka, że jeżeli , to .
Dowód:
10 Rozdział 1. Grafy skierowane
Jako dowód przedstawimy algorytm, który odpowiednio numeruje wierzchołki gra-
fu kolejnymi liczbami naturalnymi. Najpierw sa numerowane i usuwane z grafu wierz-
�
chołki, do których nie wchodza żadne kraw� Po usunieciu tych wierzchołków i
� edzie. �
wychodzacych z nich kraw� znowu otrzymamy graf bez cykli, który zawiera wierz-
� edzi
chołki bez wchodzacych kraw� Teraz te z koleji wierzchołki sa numerowane kolejny-
� edzi. �
mi numerami i usuwane z grafu, i tak dalej aż do ponumerowania wszystkich wierzchoł-
ków.
Rysunek 1.4: Graf acykliczny

Przykład 1.9 Zastosujmy powyższy algorytm do grafu z rysunku 1.4. Wierzchołkami bez

wchodzacych kraw� sa i . Przypisujemy wiec i oraz usuwa-
� edzi � �

my i z grafu wraz z wychodzacymi z nich kraw� Teraz wierzchołek nie ma
� edziami.

wchodzacych kraw� przypisujemy mu i usuwamy z grafu. W dalszych kro-
� edzi,

kach algorytm przypisze wartości , oraz . Ostatecznie hunkcja
ma postać:
v s a b c d t

1 4 2 3 5 6
Przedstawimy teraz algorytm wyliczajacy odległości z do wszystkich wierzchołków w
�

grafie acyklicznym. Zakładamy przy tym, że w grafie wierzchołki sa ponumerowane
�
tak, jak opisano to w lemacie 1.8. Bez straty ogólności można założyć, że jest pierwszy,
ponieważ nie ma ścieżek z do wierzchołków o niższych numerach.
Algorytm wyliczajacy odległości wszystkich wierzchołków w grafie acyklicznym
�

Dane wejściowe: acykliczny graf skierowany , długości kraw�
edzi

.
Dane wyjściowe: Macierz odległości z do wszystkich wierzchołków.

dla każdego podstaw

;

dla każdego po kolei według numerów zrób:

dla każdego ,

1.6. Zadania 11
Udowodnimy przez indukcje, że po -tej iteracji zewnetrznej petli wierzchołki o nu-
� � �
merch od 1 do maja już prawidłowe wartości w macierzy . Po pierwszej iteracji
�

ma prawidłow� wartość . W tej iteracji petli (zakładamy, że wierzchołki o
a �

numerach od 1 do maja już prawidłowe wartości w macierzy ) obliczamy .
�

Zauważmy, że najkrótsza droga z do przebiega przez wierzchołki o mniejszych od

numerach. Niech b
edzie przedostatnim wierzchołkiem na tej drodze. Długość tej drogi
�

�
wynosi i zostanie odnaleziona w petli.
Ponieważ mamy podwójne zagnieżdżenie petli i w obu liczba iteracji jest ograniczona
�

przez , czas działania algorytmu jest .
Przykład 1.10 (kontynuacja przykładu 1.9) Jeżeli zastosujemy ten algorytm do grafu z

rysunku 1.4, to w kolejnych iteracjach zewnetrznej petli obliczy on , ,
� �

, , oraz .
1.6 Zadania

1. Narysuj wszystkie grafy skierowane ze zbiorem wierzchołków . Które
z nich sa spójne? Które z nich sa 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 sa spójne?
�
3. Narysuj możliwie jak najwiecej nieizomorficznych grafów skierowanych z trzema
�

wierzchołkami .
4. Narysuj pare różnych i izomorficznych grafów skierowanych z możliwie najmniejsza
� �
liczba wierzchołków.
�
Rysunek 1.5: Graf skierowany

5. Zastosuj algorytm Dijkstry i znajdz najkrótsza droge z do w grafie z rysunku 1.5.
� �
6. Zastosuj algorytm Forda-Bellmana do grafu z rysunku 1.5.
7. Znajdz najkrótsza droge 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ę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 jest pętla , to liczymy ją jako krawędz wchodzącą do i jako wychodzącą
grafie
z .
Zaproponuj algorytm wynajdywania cyklu Eulera w grafie skierowanym.
Które z grafów przedstawionych na rysunkach w tym rozdziale maja cykle Eulera?
�
1.7.2 Ciąg de Bruijna

Ciąg de Bruijna rzędu to cykliczne ustawienie bitów takie, że każdy ciąg bitów
występuje w tym cyklu dokładnie jeden raz jako kolejnych bitów.

Na przykład ciąg jest ciągiem de Bruijna rzędu 2 ( występuje na pozycjach 4

i 1), a jest ciągiem de Bruijna rzędu 3 ( występuje na pozycjach 7, 8 i
ciąg

1, a na pozycjach 8, 1 i 2).

Aby otrzymaż ciąg de rzędu rozważmy następujący graf skierowany G=(V,E).
Bruijna

Wierzchołki grafu to zbiór ciągów bitów długosci . Dwa
wszystkich

wierzchołki , tworzą krawędz, wtedy i tylko wtedy, gdy ostatnich

bitów jest takie samo jak pierwsze bitów . Krawędz ta jest etykietowana

ostatnim bitem .

Narysuj graf dla , i .
Udowodnij, że:

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

Etykiety każdej drogi długości tworzą nazwę ostatniego wierzchołka tej drogi.

Cykl Eulera ma krawędzi i przechodzi przez każdy wierzchołek dwa razy.

Etykiety cyklu Eulera tworzą ciąg de Bruijna rzędu .

Wyznacz ciąg de Bruijna rzędu .

Wyszukiwarka