0000090

10.3. Drogi proute. ekstremalne w sieciach cyklicznych •

W sioci cyklicznej (zowierejęcoj drogi cykliczne) odcinek drogi eketreaalnej nie zawsze jest drogo ekstremalnę między skrajnymi wierzchołkami togo odcinka. Mogę jodnak dla sieci cyk licznej być epołnlone takie warunki, że odcinki drogi eketre -molnej będę drogami ekstremalnymi.

TWIERDZENIE 10.2

Oeżoll w sieci S •    {l)> długość każdej cyklicz

nej drogi prostej jest nleujeane, to każdy odcinek dowolnej prostej drogi najkrótszej w toj cieci jest drogo najkrótszo.

Dowód :

Zołóżmy. że teza twlordzonla jeet fałszywo. Oznacza to, że przy spełnionym założeniu istnieje taki odcinek pewnej drogi najkrótszej ^_Bln(x^p,x^k ). który nie jest drogo najkrótszo między odpowiednimi wierzchołkoal.

Sytuację tako przedotuwla rys.10.9.

M

o—

Rys.10.9

O k

Droga (^urln(^xP»^x ) ekłoda się z odcinków o długościach A.B.C, 0,E. Niech odcinek <u(x_r,x_#) o długości C będzie tym odcinkiem

który nie Jeot drogo nojkrótozę łęczycą wierzchołek x_r z wierzchołkiem x_. Istnieje zatem pewna droga najkrótsze

o    •    _B k ' min* r a'

które nie może byc włóczona do drogi <u_nln(^x »^x ) zomiaot drogi

0    długoóci C ze względu na to. że niektóre jej wierzchołki bq wopólne z wierzchołkami x_x odcinko (x^p,x_r) lub wiorzchołkoml Xj odcinka (x_o,x^k). Wybieramy wóród tych wepólnych wierzchołków wierzchołok x_i nojbliżozy od wlerzchołko x^p. a wóród x^ nojbliż azy od wierzchołka x^k w drodze (^umi_n(*^P»*¹'' )• Wtedy droga ć^A«in(^xr'^xo) ⁿⁱ⁰ ®^{a w}°P^ólny^ch wiorzchołków z odcinkami (x^p,x₁)

1

Możliwo przebiegi (ryo.10.9) drogi (U_Bln(x_r,x_B) cg noetę-pujpca (oznaczenie długoóci poszczególnych odcinków)!

1/ F, C i 2/ H. K i V F. L, K /

4/ H. M, C.

W każdym z tych przypadków otrzymamy aprzecznoóć z założeniem, że (^_Bln(^xP*^xk) J®^ot drogo nnjkrótozę łęczęcę wierzchołek x^p z wio rzchołklom x^k :

1/    O ♦ CIO oraz F ♦ C<C, czyli C<C -    F. Zatem    O+C    > F

i można    by uzyekać drogo proeto o długoóci A ł    D ♦ F ♦ ECA    ♦

♦B*C«0*£, a więc krótezo od drogi ^^umln(^xP.^xk)»

2/ H ♦ 0 > O oraz H ♦ K < C, czyli H<C - K. Zatem B*C>K 1 droga proata o długoóci A ♦ K ♦ O ♦ E Jeat króteza od

3/F»L*B>0 oraz F-a L ♦ K<C, czyli F ♦ L<C - K. Zatem B ♦ C>K i otrzymujemy przypadek 2.

4/    H ♦ 0 > O 1 C ♦ B > O oraz H ♦ M ♦ C    <C. Stfd

H> -    B,    G> - O orez -B + M- 0<C, a zatem    M < B ♦ C    ♦ O    1

można by skrócić drogę najkrótezg tnorzgc drogę o długoóci A ♦ M 4 6.

Sprzecznońć uzyokana we wezyotklch możliwych przypadkach prze -biegu drogi najkrótszej <^aa,i_n(^xr*^x#) kończy dowód twierdzenia. TWIERDZENIE 10.3

3**eli w a la cl 6 • <C,fl. {l}> długoóć każdej cykllcz-noj drogi prostej jaat niedodatnia, to każdy odcinek dowolnej, prostej drogi najdłuższej w tej alecl jeet droga najdłuższa.

179