0000106

Rys.13.1

Przepływ** zaepokajajfcym w olocl S [14] nazywamy każdo funkcjo f « U—►SI '•'{o} spełniajoco wa -runkl

1° A 0 4 f(x,y) 4h(x,y) .

<*4>€U

, o

A 2lf(*.y) - IZ ^f(*.x) • «(*) ,

xex yer\x)    _zcr-i(x)

gdzie i P(x) - zbiór wierzchołków naatopników wierzchołka x grafie G zapisanym w poetacl<X,P> ;

r.x-z^x<

zbiór wierzchołków poprzedników wierzchołka

r"^ł(*)

w grafie G zapleanya w poetacl

<x. r*.¹) ,

,-l

: X- 2'

Problem wyznaczenia przepływu zaepokajajocego Jeet równo -ważny problemowi wyznaczenia przepływu makeyaalnego w elecl ”poozorzoneJ* S* (rye.13.2)

S* ■ G* , {a*] ,{h* , k} _# gdzie G* «<X*, U*> - graf Oorge’a bez pętli i

** ■ *^u{^,0*^toł *

u* • UuU_fl^U_t t

^Um " {<V> « "tM}< U_t • {<t.t₀> » tei),

h(*.y)	dla	<x,y>ŁU j
My)	dla	<*.y> ;
-•(*)	dla	<x.y> £Ut
M*.y)	dla	<x.y>eu ł
0	dla	<x,y>CU1|uU1

Ryt.13.2

Dok widać, przopływ zoopokejaJęcy Joot wyznaczany bez uwzględnienia kosztów tranoportowych k(x,y).

Po wyznaczeniu przepływu nakeyaalnago f* w elecl S* oprov/-dzamy, czy

A f"(x,y) - h^r (x.y)

Oeóli warunek tan jest spełniony, to przepływ zaapokajajacy w eiocl S aa wartodcl równe f“(x,y) dla <x,y> CU. .*/ przeciwnym wypadku nie Istnieje przepływ zaspokajaj«cy w eieci S.

EZ •(*)

*• M

dla x ■ e„ o

dla x . t₀

;

;

211