0000109

4° Stertując z ostatnio otrzymonego przepływu (dla wszystkich łuków sieci S*) wyznaczamy nowy przepływ maksymalny f, realizując procedurę cechowania z algorytmu wyznaczenie maksy-■sinego przepływu w podsieci łuków dopuszczalnych. Po uzyskaniu togo nowego przepływu Baksyaalnego, zapamiętujemy cechy uzyskane w ostatnia kroku cechowania, wierzchołki ocechowano w tym ostatnim kroku tworzy zbiór Xj, a nleocechowane - zbiór X₂ (XjC/Xj • X).

Pytamy, czy wszystkie łukl <x,t> , xtT są nasycona?

TAKt KONIEC - otrzymany przepływ na zbiorze łuków U Jest

przepływem zaspokajającym o minimalnym koszcie w sieci S. NIE i Pytamy, czy V •    ?

TAKI KONIEC - nie latnloje przepływ zaspokajający w sieci S

NIE i Przechodzimy do punktu 5°.

5° Zmieniamy potencjały X(x) wierzchołków w następujący spo-

oób t

Wyznaczamy zbioryt

Aj -{<x.y>tU*i X€ Xj, ytx₂, k* (x,y)>I (y) -'3T(x)}ł Aj .{<x,y>£U*t x£X₂, yeXj. k*(x,y)<S(y) - 3f(x)}.

Następnie wyznaczamy i

^£x *1 ^Bif\ [^k*(x.y) - (*(y> - *(*>)]. 8dy Aj / 9 i

Ody Aj - 9 i

min [(X(y) -X(*)) - $ (k.y)1.    \ t 9 i

^Ux4^>eA*    ody Aj - 9 ;

cT ■ min |dj. tfjj.

Zwiększamy o wartość 6 potencjały 3C(x) wierzchołków nalatę -

cych do zbioru X₉. Z nowymi wartościami potencjałów przechodzimy

o ^

do punktu 3 •

Przykład 13.1

Wyznaczymy opisanym algorytmem przepływ zaspokajaj«cy o najmniejszym koszcie w sieci S • <G, (a), {h,k}> przedstawionej na rys.13.3. wartości a(x) sę przedstawiona przy wierzchołkach, wartości h(x,y) przyjęto jako nieograniczona (w prostokątach), wartości k(x,y) sę przedstawiona w trójkątach.

Ryt.13.3

Po poszerzaniu elaci 8, o wierzchołki e 1 t_Q oraz zbiory łuków U_B 1 Ufc. Ot rzymujeay eleć S* • <G? {a*’} ł « k*}> przodoto -wionę na rys.13.4. Wartości funkcji ł? przadatawlona a« w prostokątach, a wartości k* w trójkątach.

Ryt.13.4

Przyjaujany wartości potancjałów X(x) ■ 0 (liczby w kółkach przadatawiających wlarzchołkl alacl na rye.13.8), • zbiór łuków dopuazczalnych {<x,y>} (przaz która aoina caohować wlarzchołkl zgodnla z procadurą wyznaczania przapływu aakayaalnaflo) wyznaczaay z₀odnla z warunklaa k(x,y) - X(y) -T(x)i (patrz ryt.13.5).    ♦

217