Network Flow
-
network¡Gdirected graph with S¡Gsource +capacity
T¡Gsink
-
flow f¡Gexist dege e, 0¡Øf(e)¡Øc(e)
exist vertex v¡Ús,t ¡÷ £Uf(i,v)=£Uf(v,j)
i j
value of f=|f|=£Uf(i,t)=£Uf(s,j)
i j
-
Maximal flow problem¡Gfind the flow with max value
cut(x,x)¡Gx=v-x
c(x¡÷x)=£Uc(v,w)¡Gcut
capacity
v,w
f(x¡÷x)=£Uf(v,w)¡Gflow across the
cut
v,w
_
x x
|f| = 14
where v belongs to x,
w belongs to x
Lemma¡G|f|=f(x¡÷x)-f(x¡÷x)¡Øc(x¡÷x)
pf¡G|f|=|f|+0+0=£Uout(v)-£Uin(v)=f(x¡÷x)-f(x¡÷x)
s,a,b s,a,b
-
Max-flow,min-cut Theorem (Ford,Fulkerson)
maxflow¡ö¡÷|f|=c(x,x)
12,5 8,3 7,2
c,f
S¡X¡÷a¡X¡÷b¡X¡÷t
+5, ¡X¡÷f(e)<c(e)
+7 +5 +5
12,5 8,3 7,2
c,f
S¡X¡÷a¡X¡÷b¡X¡÷t +3, ¡ö¡Xf(e)>0
+7 -3 +5
find possible augmenting path, increase
flow
4 10 5
12 7
s ----> c ----> d ----> a ----> b ----> t +4
15 8
3 6
10
s ----> a ----> b ----> c ----> d ----> t +3
12 5
3
s ----> a ----> b ----> t +4
9 -4
7
s ----> a ----> d ----> t +4
F = 14
Irrational Capacity: might never terminate
Even Integral capacity: 2M increments
-
Edmond, Karp:
-
Breadth-First-Search + shortest path T = O(V3E)
-
Increase the Flow by Largest amount
-
priority-first-search implementation:
-
k->t size[k,t] >0 => priority = sizepk,t] - flow[k,t]
k->t size[k,t] <0 => priority = -flow[k,t]
if priority < val[k] then priority = val[k];
val[k]=Max increase S¡÷k
-
search stops when sink found;
-
Efficient in practice.