Network Flow

Terms:

• A Flow in graph G must satisify 1) capacity conditions. For each e belong to G, 0<=f(e)<=Ce. 2) conservation conditions. For each node v other than s and t, the flow value over all edges entering node v equals the sum of flow values over all edges leaving node v.
  
• The capacity of a cut, denoted as c(A, B), is the sum of the capacities of all edges out of A.
  

Properties:

• The residual graph Gf has at most twice as many edges as G.
  

The value of every flow is upper-bounded by the capacity of every cut. Let f be any s-t flow, and (A, B) any s-t cut, Then the value of flow v(f) <= c(A, B) , which is the capacity of a cut (A, B).

Max-Flow Min-Cut Theorem

In every flow network, there is a maximum flow f and a minimum cut (A, B) so that v(f) = c(A,B). There can be many minimum-capacity cuts in a graph G. All edges out of A are completed saturated with flow, while all edges into A are completely unused.

Ford-Fulkerson Algorithm: this algorithm will terminate when there is no s-t path in the residual graph. The algorithm is as follows.

Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph Gf
...Let P be a simple s-t path in Gf
...f'=augment(f,P) // the running time for this helper function is O(m)
...Update f to f'
...Update the residual graph Gf to be Gf'
Endwhile
Return f

Helper function
augment(f,P)
..Let b = bottleneck(P,f)
..For each edge (u,v) in P
....If e=(u,v) is a forward edge then then
......increase f(e) in G by b
....Else ((u,v) is a backward edge, and let e=(v,u))
.....decrease f(e) in G by b
....Endif
..Endfor
..Return ()






Edmonds-Karp Algorithm