0000111

Startujęc od poprzedniogo przepływu stwlerdzaay, Ze Joot on równiei przepływom naksyaelnyn przy zbiorze łuków dopuszczał -nych przedetowionya na rys.13.8. Netoaieot zbiór Xj zalśnił się

^X1 " { W^X2*^X6)

*1 ■ {<^xj»^x4^ » ^^xj*^x5) • ^^x2*^x4^ ' ^^X2*^X5^}

Wortoóci k* (x,y) - (X(y) - I(x))    09 odpowiednio równe

{5. 8. 1. l)

^Ól * ¹

*2 ■ P. Zatow 6• 1    1 wartoóć <5 dodajeay do wierzchołków

x£X*\x_i • |^x3^,X4»^X5»*₀} •

Otrzymujemy nowy zbiór łuków dopuszczalnych (rys.13.9).

Stortujoo od ostatniego przopływu wyznoczoray przepływ »okoymol-ny (przodstowiony dla całej eiacl no rya.l3.iO). Przepływ tan noeyca wszystkie łuki dochodzące do odpływu t₀. Oest to zaten przepływ zoepokajajfcy o minimalnym koszcie.

Koszt całkowity tego przepływu Jest równy

ZZ f*(x,y) I? (x.y) - 1.1 ♦ 1*5 ♦ 1*0 • 6

<x,y>eU

221