Matematyka Dyskretna - Grafy.pdf - Matematyka dyskretna - Minnie_

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.

chołka

przykład ciag wierzchołków

stanowi cykl w grae z rysunku 1.1. Krawedz typu

Rozdział 1. Grafy skierowane

Denicja 1.2 Graf skierowany jest (silnie) spójny, jezeli dla kazdych dwóch jego wierz-

chołków

istnieje droga z

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

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 < ,

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

Rysunek 1.2: Graf z długosciami krawedzi

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

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 .

Matematyka Dyskretna - Grafy.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: