0000087

nic jest drogę ekstremalna, natomiast ^U_eKtr(*_r^,x»^ * °* ^Wo “ boc ocyklicznoścl aieci odcinek U jeot •zbocznikowony• lopazym w oenalo długości drogi odclnklom O i może być nim zastępiony.

.. wyniku uzyskalibyśmy drogę lepszo, złożono z odcinków A,D,C od drogi ekstremalnej A.B.C.

Uzyakona sprzeczność kończy dowód twierdzenia.

W n 1 o a o k li Ola każdego wierzchołka x^p eleci S •

•    (lj> lotnie jo dondryt T • <X_T#U_T,P_T> o korzonlu x^p.

otanowięcy podgraf częściowy dlgrafu C ■ <X,U,P> , taki że X_T jeot zbiorem wierzchołków oalogalnych z x^p. a każda droga w tym dondryclo ^u(x^p,x) jaat drogo oketroaeln# w alacl S. ł#-czqcq wierzchołek x^p z wierzchołkiem x.

•V n 1 o a a k 2 i Ola każdego wierzchołka x^k rozważanej a leci iotniejo antydendryt o korzeniu x , atanowi#cy podgraf częściowy dlgrafu tej cieci, taki ża zbiór jago wierzchołków otanowię wierzchołki, z których jeat oaiagalny wierzchołek x*. a każdo droga w tya antydondrycla (U(x,x^k) Jeot drogo ekotre-aolno w nieci, łęczoco wierzchołek x z wierzchołkiem x^k.

Dandryty i antydendryty, o których mowa wo wnioekech 1 1 2 nazywane oę mekeymalnymi dendryta-al (antydendrytami) dróg ekstra-m a 1 n y c h. Słowo mokaymalny oznacza, że zbiory ich wierzchołków o o maksymalne.

Algorytmy wyznaczania wszystkich dróg akatreaalnych od (do) ustalonego wierzchołka oprowadzają się do wyznaczonia powyższych dendrytów (ontydondrytów). Algorytmy ta wykorzyotujo metodę programowania dynamicznego i dzięki temu sprowadzaj# olę do Jednokrotnego cochowanie wiorzchołków cechami podwójnymi, których okładowe maj# sana funkcji F*(x) i u*(x). Oednokrotność cechowania wynika z możliwości podziału zbioru wierzchołków na warstwy. Dzięki tomu czas niezbędnych obliczań przy realizacji procedur algorytmów rośnie w zsaadzla tylko proporcjonalnie wraz z ilości# wierzchołków sieci. Zopownie to ich duż# ofektywność.

W colu przedstawienia tych algorytmów zootan# podane niektóre uwagi, dzięki którym można będzie znacznie uprościć formalny ich zapis.

Uwaga li Algorytm zootoeowony w przykłodzle 10.1 nie wymogoł założonia, że graf C sieci S •    (l)> Jaat unl-

•

grafem. Ookc graf G był dopuozczalny multlgrof oklerowany. Spowodowało ta konlocznoóć operowania w olgorytnla zorówno zbio -ron wierzchołków W jnk i zbiorea łuków U, co znocznie komplikowało stosowano tern zopiey formalne. Zouważmy Jednak, to w przypadku rozpatrywanych zadać aotomy zawoza dana multlsloć zastę-pić odpowiednia zaotępczę unisiocię. Mianowicie, jetall ustoll-oy, te chodzi nam o drogi najdłutsze. to dlo kotdej uporządkowanej pory wierzchołków <x_1#Xj) motemy ze zbioru łuków łączących to wierzchołki wybroć łuk o maksymalnej wartodci l(u). W ton eponób otrzymujemy zaotępcze uniaieć, w której kntdy łuk Jeot równowatny parze uporzadkowonej wiorzchołków incydentnych z nim. Analogicznie motomy'zredukować eloć, gdy poozukujemy dróg najkrótszych, z tya te wówczas pozootawionry łukl o mini -melnej wartodci l(e). W ten epoeób algorytmy motemy opisywać przy załotenlu, iB graf elecl Jest unigrafe* i zamiast cechy u*(x) motemy podawać numer wierzchołka y(x), dó którege (bądź z którego) prowadzi łut u*(x).

Uwaga 2i Zouwotmy, ta Joto li wprowadzimy pojęcie antydrogi okredlonej Jaka claf wierzchołków i łuków ponumerowanych odwrotnie nit cięg wierzchołków 1 łuków donej drogi (od końco de początku), te antydroge Jest najdłutsze (najkrótsza) wtedy i tylke wtedy, góy odpowiadające jej droga jest najdłutsze (najkrótsza). Dzięki temu motemy stosować metody programowania dynamicznego zarówno przy numeracji etapów rosnącej w kierunku zwrotu łuków sleel w układzie warstwowym, J-k i przy numeracji przeciwnej, V» pierwszym przypadku będziemy ekstremo-lizować etapowa funkcje celu pe zbiorze następników aktualnego wierzchołka (przy wyznaczaniu cechy F(x)), a w drugim przypadku po zbiorze poprzedników, w tya celu grof Błoci będzie wygodnie przedstawiać w zapisie G • <X.P> j Pi X — 2^X, gdy* zgodnie z uwagę nr l jest on unigrafem 1 mota być zadany za pomoc# binarnej macierzy relacji A(0) -

X góy ajf IMWj)

•lj "

;0 w przeciwnym przypadku

173