0000092

Oznacza to, 2e

F(_Xj)> F(_Xl) ♦ 1( <X₁.*_l4ł> )

Otrzymujemy eprzoczność, która kończy dowód twlerdzonia. TWIERDZENIE 10.5

Dendryt T o korzeniu x^p zewiersjęcy wszystkie wierzchołki oelęgolne z x^p w elecl S    {l)> takiej.

Ze koźda prosta droga cykliczna tej elocl no długość nledodatnlę, a G Jeat unigrofen, Jeot nakoymalnym dondryte* dróg najdłuższych w tej alecl od wierzchołka _X^p wtedy i tylko wtedy, gdy dlo keZdoj cięciwy u ■    tego dendrytu epołniono Jeat nierówność

F(_Xj) > F(_Xl) ♦ 1( < _Xl.Xj> )

Dowód i

Tworzęc oieć *3 • <G.{J, {-l)> etrzynujemy założenie 1 tezę dowiedzionego twierdzenia 10.4. Kończy to dowód twierdzenia.

Zatoń twierdzenie 10.4 i 10.5 oq symetryczne względem eie-ble. Stanowię one podstawę algorytnów wyznaczania dendrytów dróg ekstremalnych w sieciach cyklicznych. Wystarczy przy tym ograniczyć się do omówienia elgoryteu wyznaczania dendrytów dróg najkrótszych w sieciach o nleujemnych długościach dróg cyklicznych.

Procedura tego algorytmu ea charakter lteracyjny. Polega ona na przyjęciu dowolnego dendrytu i kolejnej wymianie łuków tego dendrytu na cięciwy, które nie spełniaj# tezy twierdzenia 10.4.

10.3.1. Algorytm wyznaczania dendrytu dróg najkrótszych w sieci cyklicznej

Danej Sieć S ■ <G,(ł, {1)> , dla której będż 1>0, będź wozyotkie drogi cykliczne w niej zawarte maję nieujemnę długość. Ustalony wierzchołek _X^p.

Procedura. Oędzleny cechować wierzchołki podwój -nyoi cochoml (F(x), g(x)) zmniejezejęc itorecyjnie wortoścl F(_X)*

1° Wierzchołkowi x^P nadajemy cechę podwójny (0. ♦ ). o pozostałym wiorzcholkom oloel cechy (*© , ♦).

2° Zmnlojezaey ltcracyjnlo wartości lewych coch F(x) wierzchołków różnych ad x^p w nostępujgcy epooóbs Dla łuków u • <x,y> digrafu G takich, żo

F(y) - F(x)> l(<x,y> )

nadajemy wortoóć lewoj cechy wierzchołka y równo F(y) « • F(x) ♦ 1( <x.y> )

Ooko wartoóć prowoj cechy g(y) wierzchołka y wpleujemy numer wierzchołka x, z którogo nadano nowę wortoóć lowej cechy wierzchołkowi y. Czynnoóci opioene w tym punkcie kon -tynuujeoy, aprawdzajoc wezyatkie łukl po każdej zalanie cechy, dotgd aż nie będzie można zaniejezyć lewej cechy żad -nogo wiorzchołko.

3° Tworzymy maksymalny dendryt najkrótszych dróg prostych w ton apoeób, że do każdego wierzchołka y doprowadzamy jeden łuk od poprzednika x ■ g(y). Do dondrytu wejdę wazyatkle wlorzchołki o cechach różnych od (oo, ♦ ). Oługoóci oróg (^UBln(^xP'^x) ^r6wn® oatatnlm cechom F(x).

U w o g a li W danej oieci S, od uotalonogo wierzchołka x^p, może ietnlać wiole różnych dróg nojkrótozych do pewnego wierzchołko x. Przedotowiony olgorytm wyznacza tylko Jodnę z tych dróg (przypadkowo wybrano w wyniku przypodkowej kolejnoócl zmnlojezania lewych cech wierzchołków).

Uwago 21 Algorytm charakteryzuje się wielokrotnym, iterecyjnym cechowaniem wierzchołków. Deżell zotem występuje w praktyce potrzebo wyznaczenia tylko Jedne i drogi najkrótszej, łęczęcoj ustalono parę wierzchołków (x^p,x^k), to nie możemy przsr-wać^procosu cechowania z chwilo pierwszego zmniejszenia cechy F(x ). Proceduro punktu 2° algorytmu musi być kontynuowano do końca i dopioro wtedy zamiast całego dendrytu możemy wyznaczyć tę Jodnę, poszukiwano drogę wodług prawych cech wierzchołków 8(*).

183