0000091

Dowód :

Dożęli dla danej elecl S • <G.,p, {1) > utworzymy olać S ■

■ <C,p. {-l)> , to każda droga nojdłużazo w aiecl 8 Jcot drogę najkrótozę w eiecl 8 i no odwrót. Tworzęc zoten tekę cioć dla •leci założonej w twierdzeniu, otrzymujemy dowiedziono tezę twlerdzonla 10.2.

W n i o e e k 1: Drogi ekstremalne, określone założeniami twierdzeń 10.2 i 10.3 można przedstawić za pomocę makoymbl -nych dendrytów 1 antydondrytów dróg ekstremalnych, analogicznie jok dla sieci acyklicznych.

Wniosek 2: W oieci S -<.G.P, (l}> z nleujemnę funkcjo 1 (1> O) każdy odcinek dowolnoj, prostej drogi najkrót-ozej Jest drogo najkrótszo. Natomiast w sieci z niedodotnię funkcję 1 (li O) każdy odcinek dowolnej, prostej drogi najdłuższej jest drogo najdłuższo, wniosek ten wynika z togo. żo dla takich funkcji 1 spełnione oę odpowiednio założonia twierdzeń 10.2 1 10.3.

Metoda wyznaczonio dróg ekstremalnych, dla przypadków określonych założeniami twierdzeń 10.2 1 10.3 oraz zołożonlaml we wniosku 2, polega na wyznaczaniu odpowiednlogo dondrytu dróg ekotromolnych dlo założonego wierzchołka poczętkowogo x^p. Dod-nak wyznaczenie takiego dendrytu nie może być dokonane w ten epooób, jak to było opioono dlo oieci acyklicznych. Sieć cyk -liczna w eenoie dróg nio może bowiem być rozłożone na warotwy bydęce podotowę zaotooowanej poprzednio metody programowania dynomicznego.

Tworzenie dendrytu dróg ekotromolnych w oieci cyklicznej opiorą oię no innej zasadzie. Dlo jej wyjaśnienia rozwożymy przypadek dróg nojkrótozych w sieci, epełniajocych zołożenlo twiordzenio 10.2. Weźmy dowolny dendryt T w tej.sieci o korzeniu x^p. Długość drogi w tym dendrycle ^t(x^p,x) od wierzchołka x^p do wierzchołka x oznoczymy przez F(x). Powstaje pytonietkie-dy toki dondryt jest maksymalnym dendrytem dróg najkrótozych od wierzchołka x^p do wierzchołków oolęgalnych z x^p w rozpatrywanej sieci? Odpowiedź daje naotępujoce twierdzenie.

TWIERDZENIE.10.4

Oondryt T o korzeniu x^p, zawiorojęcy wozystkle wierzchołki oslogelne z x^p w slocl S • <C,P, {l}> takiej, że

każdo prosta droga cykliczna tej alacl ma niaujaany długość, a C Jest unigrofcm, Jest maksymalnym dendry-tem dróg najkrótozych w toj sieci od wierzchołka x^p wtedy i tylko wtody, gdy dle keżdoj cięciwy u •

-<x₁,x_J> tego dendrytu spełniono jest nierówność

P(*_x) ♦ 1 (

O o w ó d »

Należy dowieść dwie lnplikocjo - prosty i odwrotny. Ola obu zoatoaujemy dowód apagogiczny.

Załóżmy, że T Jeat dendrytea dróg najkrótszych i istnieje tako cięciwa u ■ <x_l.Xj> , że

F(Xj)> F(Xi) ♦ i ( <x₁.x_J> )

Otrzymujemy natychaiast sprzeczność, bo od wierzchołka x^p do wierzchołka x^ iatniejś poza dondrytew droga krótoze ad drogi w dendrycie. Ta krótoze droga okłada siy t drogi w dendryelo ^u(x*⁾,x₁) oraz cięciwy u •    • Uzyskana sprzeczność koń

czy dowód implikacji prostej.

Załóżmy toraz, ża dla każdej cięciwy u • <x_l,x^> spełniana jaat nierówność F(x_J)4F(x₁) ♦ 1( <x₁,x_J> )    1 jednocześnie.

T nio jest dondrytom dróg najkrótszyoh od wierzchołka x^p. Wtedy iotniaje wierzchołek x tego dendrytu taki, ża droga prosta <u(x^p,x) złożona z łuków dondrytu nie Jaat drogę prosty najkrśt

Niech zatem clyg łuków U_x • {u₁,...,u₁.....u_n) określa

drogę ^_nln(x^p,x). Na nocy twierdzenie 10.2 każdy odcinak tej drogi etanowi drogę najkrótszy wlędzy odpowiedniki wiarzchoł -kaal. Zataa ciyg U_x określa równiwż drogi proste najkrótsze z x^p do wszystkich wierzchołków pośrednich x_Ł określonych tym ciy glew. Niektóra łuki u_x z clggu U_x należy do T, natomiast pozostałe muozy być clęclwaal T, ponieważ wszystkie wierzchołki oelygalne z x^p należy z założenia do T. Wybierzmy zatem łuk ^ui *^^xi*^xi4i) * ^tóry jest pierwszym lukiem (llczyc od x^p) takim, że nie nałoży do T, a drogo o ciygu łuków [u_Ł.....z

wierzchołka x^p do wierzchołka x_1+ł Jest krótsza od drogi do togo wierzchołka blegnycej po lukach dondrytu.