0000104

12.2. Przepływ dopuszczolny

bierzemy pod uwagę sieć

S • <C. {e),{l,h} > . gdzie

C ■ <X,U> , UCXU, Joet grefoa Dorgo'c boz pętli;

a i X—{-1, 0, l) ; | [x i a(x) • -1} | »|{x 1 a(x) ■ l}| • 1; l.h » U -*> SŁ*u{0} •    .

Przepływem dopuszczalnym w alecl S nazywamy każdo funkcję f 1 U    {o} epełnlajęcę noetępuję-

co dwa warunki:

i° A M*tyKf(x.yUM*.Y)

<x.y>tU

gdzioi P(x) jeot zbiorem następników wiorzchołke x w grafie 6 zapieanym w oootoci <X,p> , p: X2^X ;

_mĄ    •

p (x) J081 zbiorem poprzedników wierzchołka x w grafie C zoplonnym w postaci <X, T*^l> ,    p"¹ i X-*-2^X.

Funkcjonał v(f) nazywamy wartodcię przopływu f

ycr(ż)    ZCP‘'(4;

gdzie et X i a(a) ■ 1. nazywamy źródłem.

Wierzchołek tcx i o(t) ■ -1 nazywamy odpływem.

W celu okorzystanla z algorytmu wyznaczania opływu, dla wyznaczonio przepływu dopuezczalnego, modyfikujemy siec S tworzęc eleć S* w naatępujęcy oposób (rys.12.i).

Rys.12.1

20C

i (*.y>

fi (*.y) •

0 1* i	h*
M*.y)	dla <x,y> / <t.s>
0	dla <x.y> • <.t,e>
h(x.y)	dla <.x.y> / <t,e>
oo	dla <x.y> ■ <t,e?

W ton epooób S* ■ <G,p,{l*, £}>.

W tok zmodyfikowanoJ sieci wyznaczamy opływ.

Oożoli opływ lotnioJo, to ueuwejgc dodany łuk <t,*> wrocamy do pierwotnej oloci S, o wartości opływu f określojo przopływ do-puczczolny od źródło o do odpływu t. dożoll natomiast w oloci S* opływ nie lotnlojo, to nio lotnioJe przopływ dopuozczalny w eiocl S.

12.3. Przopływ maksymalny w oloci S • <G, (o), (1. h}>

Oznaczymy przez P zbiór przepływów dopuszczalnych f w rozpatrywanej oloci S. Przepływem maksymalnym w tokioj eiocl nazywamy przopływ f_mox opołniajocy wa-runok

■•«*<*>

Przepływ mokoymolny możemy wyznaczyć wykorzystując algorytm wy-znoczonia przopływu dopuezczalnogo (punkt 12.2) oroz zmodyfi -kowany algoryta wyznaczania przepływu maksymalnego.

Proceduro :

(l) Wyznaczamy przepływ dopuszczalny f.

dożęli przopływ dopuszczalny nie lotnlojo, to nie istnieje również przepływ maksymalny (KONIEC).

(D ^Pr*yJ*ujoc f Joko przopływ początkowy, realizujomy proce -durę wyznoczanio przepływu moksymalnogo, z tym że opraw -dzajgc ocechowany i nieoprewdzony wiorzchołok x cuchujomy

207