DSC00321 (5)

TAK: cechujemy wierzchołek y cechu

(**, min {*(x), h(x, y)-/(x, y)})

wierzchołek y> staje się ocechowany i niesprawdzony.

NIB: rozpatrujemy pozostałe nieocechowane następuik) wierzchołka v Jeżeli y jest ostatnim z nich, to przechodzimy do b). b) Dła każdego r, który jest nieocechowanym poprzednikiem a, spraw* dzamy, czy

/U.x)>0?

TAK: cechujemy wierzchołek r cechą

(x’,min{i(.v)_ł/(i,x)})

wierzchołek z staje się ocechowany i niesprawdzony.

NIE: Rozpatrujemy pozostałe nieocechowane poprzedniki wierzchołka a*. Jeżeli z jest ostatnim z nich, to wierzchołek ,v sti\je się sprawdzw uy i skok do punktu 3.

5. Zmieniamy aktualny przeplyw/na przepływ/', o wartości i*(/^ł) •»>(/)+«» gdzie    w następujący sposób: Rozpoczynamy od wierzchołka t.

Jeżeli t ma cechę 0‘*» *(0)» to dla luku <)• ,.t> nadajemy wartość/‘(.v, O •* ^mAy* 0+c. Jeżeli t ma cechę O‘*»*(0)» to dła luku \i,y) nadajemy wartość    Następnie przechodzimy do wierzchołka v.

.Jeżeli y ma cechę (.v*,eG’))» to dła luku (,\\y> nadajemy wartość f\x,y)-/(a‘,.v)+«. Jeżeli y ma cechę (x^m‘_te{y))_% to dła łuku vy».v> nadajemy wartość /'O’* -v)    A')-r. Następnie przechodzimy do

wierzchołka x i postępujemy analogicznie, aż dojdziemy do źródła i. W ten sposób został zidentyfikowany łańcuch powiększałny i zmieniony przepływ na łukach tego łańcucha o wartości ę » «(ł), Kasujemy cechy wszystkich wierzchołków i przechodzimy do punktu 2, t otrzymanym nowym przepływem.