0000102

5° Zmieniamy aktualny przepływ f na przepływ , o wartości v( f * ) • v(f) ♦ £ , gdzie C» L(t), w następujący opoeób i Rozpoczynamy od wierzchołka t. Dołoll t aa cechę (y*, t(t)), to łukowi <y,t> ntidajamy wartość f' (y • t) • f(y,t) ♦ £ . Detali t aa cechę (y~,C(t), to łukowi <t,y> nadajeoy wartość f'(t,y) • f(t,y) - t . Następnie przechodzimy do wierzchołka y. Dożęli y aa cachę (x*. c(y)). to łukowi <x,y> nadajemy wartość f'(x,y) ■ f(x,y) ♦ C . Dożęli y aa cechę (x“, C(y))» to łukowi <y,x> nadajeay wartość f'(y,x) ■

■ f(y.x) - t • Naotępnle przechodzimy do wierzchołka x 1 postępujemy analogicznie, aż dojdziemy do źródło a. V/ ten opoeób zoetał zidentyfikowany łaócuch powlękazalny 1 żale* nlony przepływ na łukach togo łańcucha o wartości £ ■ £(t). Kasujemy cochy wszystkich wierzchołków 1 przechodzimy do punktu 2°, X otrzymanym nowym przepływem.

Rozdział 12

OPŁYW W SIECIACH Przyjmiomy do rozwotoń aleć

S -<C.p. {l,h)>

gdzie C ■ <X,U> , UCx«X (graf Berga'a baz pętli), l.h i

04 1 (x,y) 4 h (x,y)

Ola aleci togo typu zdefiniowany Jeet opływ [l4] w noetępujęcy apoaóbt O p ł y w o ■ nazywamy kaldę funkcję f i U-*-£V{0) » opełnlojęcę dwo warunki i

i° A l(x.y) 4 M*«y) * ^h(*.y)»

<x,y>6U

2°    f(x,X) - f (x,x) . o ,

gdzie

f(x,X) - ZZf(x.y)

yCPoO

f(X,x) - C,f(x.x)

Z4P'U)

^przY 'y^-1 P(x) - zbiór wierzchołków "następników" wierzchołka x w grafie G zoplaanym w poatacl <X,T>    ,

gdzie P i X 2^X ;

r"^ł(x) “ zbiór wierzchołków "poprzedników* wierzchołka x w grafie C zapleanyn w poetecl <X, P"¹). gdzie P“^ł , x-—2^X.

203