Matematyka Dyskretna (Grafy).pdf
(
91 KB
)
Pobierz
Md10.dvi
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. Kazdej krawedzi przypiszemy długosc (wage) i algorytmy beda szukac
drogi, dla której suma długosci krawedzi jest najmniejsza.
1.1 Grafy skierowane
Denicja 1.1
Graf skierowany (zorientowany) to dowolna para
, ze sko nczo-
nym zbiorem wierzchołków
i zbiorem krawedzi
.
Rysunek 1.1: Graf skierowany
W grae skierowanym krawedz
jest skierowana od wierzchołka
do wierz-
ko ncem. Na
rysunkach krawedzie skierowane bedziemy przedstawia c jako strzałki. Droga w grae
skierowanym jest to ciag wierzchołków
. Wierzchołek
nazywamy poczatkiem krawedzi, a wierzchołek
, taki, ze dla kazdego
(
*),+
,
wierzchołki
,
sa połaczone krawedzia, czyli
. Droge
nazywamy cyklem jezeli
, oraz wszystkie wierzchołki
sa rózne. Na
jest cyklem w grae z rysunku 1.1. Dla grafów
skierowanych dopuszczamy cykl złozony z dwóch wierzchołków, na przykład ciag
, w której poczatek i koniec
pokrywaja sie, nazywamy petla. Mozna przyjac, ze petla jest cyklem długosci jeden.
3
chołka
przykład ciag wierzchołków
stanowi cykl w grae z rysunku 1.1. Krawedz typu
4
Rozdział 1. Grafy skierowane
Denicja 1.2
Graf skierowany jest (silnie) spójny, jezeli dla kazdych 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 grae
Przypuscmy teraz, ze kazdej krawedzi
przypisano długosc (wage)
. Dopuszczamy
przy tym ujemne długosci. Dla kazdej drogi w grae
7
%#$#$#%
zdeniujmy jej długosc jako sume długosci krawedzi, czyli
/
!
, droga składa sie z pojedynczego punktu, to przyjmujemy, ze jej długosc wy-
nosi 0. W tym rozdziale interesuja nas algorytmy wyznaczania najkrótszej drogi łaczacej
dwa wierzchołki
i
w grae.
Przykład 1.4
Jako przykład zastosowania algorytmu wyszukiwania najkrótszej drogi w
grae rozpatrzmy siec poł acze n, czyli graf, w którym krawedzie reprezentuj a ł acza pomiedzy
wezłami. Z kazd a krawedzi a
, ze krawedz za-
działa bez awarii. Zakładamy, ze awarie poszczególnych krawedzi s a od siebie niezalezne.
Przyjmijmy teraz długosc krawedzi
zwi azane jest prawdopodobie nstwo
jako
. Najkrótsza droga jest wtedy
drog a z najmniejszym prawdopodobie nstwem awarii.
Łatwo zauwazyc, ze jezeli w grae sa cykle o ujemnej długosci, to dla pewnych par
wierzchołków nie istnieje najkrótsza droga miedzy nimi. Powtarzajac przejscie wzdłuz
cyklu mozna wtedy otrzymywac drogi o długosci dowolnie małej. Dlatego w dalszej
czesci bedziemy zakładac, ze w grae wszystkie cykle sa dodatniej długosci.
Problem znajdowania najkrótszej drogi w grae nieskierowanym, jezeli wszystkie
krawedzie maja dodatnie długosci, mozna sprowadzic do przypadku grafu skierowane-
go. Wystarczy kazda krawedz
<
zastapic przez dwie krawedzie
i
etapie wyznaczymy najkrótsza droge z
do
.
Najpierw opiszemy drugi etap, czyli jak znalez c najkrótsza droge z
do
, jezeli znane
sa odległosci z
do wszystkich wierzchołków grafu. Algorytm ten bedziemy opisywa c
przy pomocy przykładu grafu z rysunku 1.2.
Dla prostoty algorytmu przyjmujemy
. Załózmy, ze
macierz
zawiera odległosci od
do wszystkich pozostałych wierzchołków grafu.
, jezeli
2
<
,
4
Jezeli
. Jezeli
w grae sa krawedzie o ujemnych długosciach, to sposób ten prowadzi do powstania cykli
ujemnej długosci.
Opisane tu algorytmy składaja sie z dwóch etapów. W pierwszym etapie wyznaczamy
długosci najkrótszych dróg z
do wszystkich wierzchołków w grae. A dopiero w drugim
1.3. Algorytm Forda-Bellmana
5
Rysunek 1.2: Graf z długosciami krawedzi
v
s a b c d t
0 1 0 -1 1 2
zawiera odległosc
od
, czyli długosc najkrótszej drogi z
do
. Przyjmujemy
. Najkrótsza
droge od
do
wyznaczamy teraz od ko nca. Najpierw szukamy przedostatniego wierz-
oraz
, jezeli nie ma zadnej drogi z
do
chołka tej drogi, pózniej trzeciego od ko nca i tak dalej. Przedostatni wierzchołek
naj-
krótszej drogi spełnia równosc
W naszym przykładzie tylko wierzchołek
spełnia ta równosc. Zauwazmy, ze isnieje
droga długosci
z
do
. Jezeli przedłuzymy te droge o krawedz
, to otrzymamy
istnieje. Jest to przedostatni wierzchołek dowolnej najkrótszej
drogi z
do
. Trzeci od ko nca wierzchołek
, czyli najkrótsza droge z
do
. Jest tez
spełnia równosc
.
Algorytm ten musi zako nczyc prace, poniewaz kolejne wierzchołki odsłanianej drogi sa
rózne. Inaczej mielibysmy cykl, co nie jest mozliwe, jezeli w grae wszystkie cykle sa
dodatniej długosci.
i tak dalej, az odtworzymy cała droge
1.3 Algorytm Forda-Bellmana
Mówiac z grubsza polega on na przyjeciu najpierw pewnych górnych oszacowa n na war-
tosci
i poprawianiu ich potem. Jezeli na jakims etapie pracy algorytmu mamy war-
tosc
, to znaczy, ze znaleziono juz droge od
do
długosci
. Jezeli pózniej algo-
rytm znajdzie krótsza droge, to wartosc
zostanie poprawiona. Znajdowanie krotszej
drogi polega na szukaniu wierzchołka
spełniajacego warunek
3#
przy tym, ze
jasne, ze taki wierzchołek
droge z
do
długosci
W naszym przykładzie jest to
W tym podrozdziale opiszemy pierwszy z algorytmów obliczania wartosci macierzy
.
Plik z chomika:
Iskraa
Inne pliki z tego folderu:
Matematyka Dyskretna.pdf
(1323 KB)
Matematyka Dyskretna Władysław Skarbek.pdf
(819 KB)
kombinatoryka1.pdf
(40 KB)
arytmetyka.pdf
(96 KB)
Wojciech Kordecki - Matematyka Dyskretna (Materiały Pomocnicze).pdf
(169 KB)
Inne foldery tego chomika:
Helena Rasiowa-Wstep do matematyki wspolczesnej
Zgłoś jeśli
naruszono regulamin