DSC00315 (5)

11.1. Przepływ maksymalny

W problemie przepływu maksymalnego przyjmuje się standardową sieć S*= <G, {n}, gdzie G jest spójnym grafem Berge'a bez pętli,.

(/>; a(x) jest funkcją opisaną na zbiorze wierzchołków, xe\V wyróżniającą w sieci.dwa wierzchołki: s — irtidlo oraz f — odpływ,

1 dla x — s

Wm $

o

-i

dia

dla

x M s, f

natomiast h(x, y), <.v, y>e U, jest nieujeraną funkcją na zbiorze łuków di* grafu G,    h(x, y) < co, której wartości są interpretowane jako przepusto

wości poszczególnych luków sieci. Jeżeli sieć 5 jest, np. modelem sieci wodociągowej, to wartość h(x,y) interpretuje się jako maksymalną, dopuszczalną ze względu na ciśnienie, intensywność przepływu wody, przez odcinek rury reprezentowany łukiem <x,y).

Przepływem w sieci S nazywamy dowolną funkcję f:U-*R spełniającą następujące dwa warunki:

2) A 1 Z /<*,>•)- Z /(z, *)» «(*)*>(/)}

**ir    *«r;‘

gdzie r_x jest zbiorem następników wierzchołka x, a f"¹ zbiorem poprzedników wierzchołka .v, digrafu sieci, w zapisie G «=* (fV, ry. Wielkość v{f) nazywana jest wartością przepływu f i łatwo zauważyć, że funkcjonał ten jest określony naśtępującó*:

.<>(/)- Z /(«.>')“ Ż /(*.*)

y«r,    t »r?¹

Sieć wraz z przepływem / może być formalnie zapisana jako Sy * <G. {a>, {/»,/»