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)
• augmenting path
         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

• Labelling algorithm¡G
find possible augmenting path, increase flow
• example

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

• Drawbacks:
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.