1.  Max Flow

1.1  definitions

• flow-network = directed G = (V,E)
• Capacities C(u,v) ³ 0 If (u,v) Ï EÞ c(u,v) = 0
• For s,t Î V let s = source , t = sink
• flow = f:V×V® R s.t.

1. f(u,v) £ c(u,v)
2. f(u,v) = -f(v,u)
3. u Î V-{s,t} s.t. å_{v Î V}f(u,v) = 0

• |f| = å_{v Î V}f(s,v) = net flow

The max flow problem has as input a flow network and as output a flow, f , with maximum net flow.

2.  Example problems

2.1  bananas

There are a set of banana producers and a set of banana consumers. We want to maximize the number of bananas succesfully fed to consumers. Make the source node connect to every banana producer with capacity = banana production quantity. Make the sink node connect to every consumer with capacity = number of bananas eaten. Connect producers to consumers with capacity = amount of shipping capacity. Solve the problem. The solution maximizes shipping consumption.

2.2  network flow with delays

Nodes are connected with some capacity and some delay. We want to mazimize the flow within some amount of time, t . Expand the graph to G×t = (V×t,E_t) . Two nodes v_t1,u_t2 are connected if (v,u) Î E and t₂-t₁ = delay on that edge. Solving this flow problem will give the solution.

3.  Algorithm

3.1  definitions

• residual capacity: f = flow on G , C_f(u,v) = C(u,v)-f(u,v)
• residual network: E_f = {(u,v) Î V²|C_f(u,v) > 0}

Given the residual network, we need to find an ``augmenting path'' which increases the flow.

• Partition A,B of V is s,t cut if s Î A,t Î B .
• Cost of the cut: C(A,B) = å_{u Î A,v Î B}c(u,v)
• In general: f(A,B) = å_{u Î A,v Î B}f(u,v)

3.2  lemma

if f a flow on G , G_f is a residual then

1. f¢ a flow on G_f iff f+f¢ a flow on G
2. f¢ max flow on G_f iff f+f¢ is a max flow on G
3. |f+f¢| = |f|+|f¢|

Proof of (1) f¢ is flow on G_f then f¢(e) £ C_f(e) = C(e)-f(e) Which implies f¢(e)+f(e) £ C_f(e)

3.3  Another lemma

"s,t cuts A,B f(A,B) = |f| .

3.4  Yet another lemma

|f| £ C(A,B)

3.5  Max flow min cut theorem

The following are equivalent:

• f is a max flow
• $ cut A,B s.t. C(A,B) = |f|
• There does not exist an augmenting path

3.6  Algorithm

1. Find augmenting path -> none means you are done
2. Calculate residual
3. repeat

Add up all the augmenting paths to get the flow.

4.  Analysis

The convergence time can be very long. For integers it can be at least proportional to |f| . If you allow noninteger capacities the algorithm may not even be convergent.