Definition of a Flow Network:
A directed graph (V,E) with the following properties:
 Associated with each edge e is a capacity c(e) , c(e)>0.
 There is a single source node s belonging to V
 There is a single sink node t belonging to V
Nodes other than s and t are called internal nodes.
Assumptions:
 All capacities are integers.
 There must be at least one edge leaving source
 There must be at least one edge entering the sink
Defining Flow:
Basically carrying traffic or flow. More formally, flow is a function mapping each edge to a value f(e) satisfying the following three constraints:
 {Capacity Constraint} For each edge e, f(e)<=c(e)
 {Skew Symmetry} For each pair of vertices u,v , f(u,v) = f(v,u)
 {Flow Conservation} For each node v other than s and t, sum of all flow going out of v must be zero. In other words, total +ve flow coming into v (or f_{in}(v)) equals total +ve flow going out of v (or f_{out}(v)).
Hence f can be both negative or positive, also called the net flow of that edge. The value of network flow is thence summation of flow going out of source.
Note: Generally flow for an edge corresponds to the positive flow.
Defining Flow between sets:
f(X,Y) = sum of f(x,y) , x belongs to X, y belongs to Y.
Some Basic Identities:
 f(X,X) = 0
 f(X,Y) = f(Y,X)
 f(XUY,Z) = f(X,Z) + f(Y,Z) if X and Y are disjoint.
 f(s,V) = f(V,t)
Proof:
f(s,V)
= f(V,V) – f(Vs,V)
= f(V,Vs)
= f(V,t) + f(V,Vst)
= f(V,t) – f(Vst,V)
= f(V,t)
The MaximumFlow Problem
Natural Goal – Maximizing the flow from source to sink without violating capacity constraints.
Note: Problem for multiple sources and sinks can be reduced making a global source and a global sink and connecting with infinite capacities.
Example: Formulate maximum flow as linear programming problem.
Designing The Algorithm:
 DP won’t work here.
 If start with a greedy approach then we can counter that by compensating some flows and directing it to other edges.
 Hence the concept of augmenting paths
Residual Graph: G^{’ }defined w.r.t. some flow f.
 Node set of G’ same as G
 Consists of edges that can admit more net flow.
 For every edge having flow less than capacity (assuming forward to be the direction of the capacity)

 A forward edge with residual capacity
 A backward edge describing the flow for that edge
 Mathematically, c_{f}(u,v)=c(u,v)f(u,v) {c(u,v) will be zero for the reverse edge in nearly all cases}
Note: If f is a flow in G and f’ is a flow in G_{f}, then f+f’ is also a flow in G. Proof is trivial using the definition of flow network.
Augmenting Flow using the residual graph:
For any residual graph G^{’ }, a simple path P with the bottleneck edge b as the minimum cost edge in P is called an augmenting path.
f_{p}(u,v): b if (u,v) belongs to P, b if (v,u) belongs to P, 0 otherwise.
Augmenting flow is defined as f’(u,v) = f(u,v)+f_{p}(u,v)
Proof of f’ being a flow:
If e is a forward edge on P > 0 <= f(e) <= f’(e) = f(e) + b <= f(e) + (ce – f(e)) = ce;
If e is a backward edge on P > ce >= f(e) >= f’(e) = f(e) – b >= f(e) – f(e) = 0;
Proof for conservation of each node:
If node not in P, no effect. If node is in P then one outgoing flow increases and one incoming flow decreases by the same amount.
Flows and Cuts:
Notion of Cut: partition the nodes into two sets S & T, s belongs to S, t belongs to T. Then (S,T) form a cut.
Identity: Flow of a cut ( f(S,T) ) equals f(s,V).
Proof:
 f(S,T)
 = f(S,VS)
 = f(S,V)
 = f(s,V) + f(Vs,V)
 = f(s,V)
 = f
Capacity of the Cut: c(S,T) sum of capacities of all edges from S to T.
Theorem: Max Flow = Min Cut for a flow network.
Proof:
 Any Flow <= Capacity of any Cut

 Trivial
 If f is maximum,

 G_{f} has no augmenting path

 Proof:

 f’ = f + f_{p} hence flow increasing with each augmentation.
 f = c(S,T) for some S,T

 Proof:

 Take S as all nodes reachable from s in the Residual Graph.
 As t is not reachable from s, S must not contain t.
 Take T as VS.
 As there are no outgoing edges from S to T in G_{f} , f(S,T) must be equal to c(S,T).
FordFulkerson Algorithm for finding MaxFlow:
MaxFlow
Initially f(e)=0 for all e in GWhile there is an st path in the residual graph G_{f}
 Let P be any (not necessarily simple, simple makes it the generic flow algorithm) st path in G_{f}
 f’= augment(f, P)
 Update f to be f’
 Update the residual graph G_{f} to be G_{f}^{’}
EndwhileReturn
Points to remember:
 After every augmentation, the flow values and residual capacities are integers
 While augmenting the flow is taken along the direction of the path.
 The total value of flow increases by the bottleneck edge of st path cost as all other points conserved
 At most F iterations where F is maximum flow.
 Hence running time at most O(mF) as BFS in O(m+n) and n<=2*m as all nodes have at least one incident edge.
EdmondKarp Algorithm for finding MaxFlow:
Same as the Generic flow algorithm, with augmentation done only with shortest BFS paths (edge weights as 1).
Running Time With This Modification: O(m^{2}n).
Proof that running time is O(m^{2}n):
 Let δ(s,v) be the level of v in BFS tree.
 After an augmentation, for each edge:

 Either a backward edge is added (if existing was forward)
 Or a forward edge is added (if existing was backward)
 Which means, in a BFS tree, if L_{i} to L_{i+1} was removed, L_{i+1} to L_{i} would be added.
 Hence, δ(s,v) must increase at every iteration.
 If an edge starting at u is chosen as the bottleneck edge, u’s level increases by 2.
 Hence a total of 2m * n/2 edges can be chosen as bottleneck.
 Total no. of iterations <= mn.
 Hence O(m^{2}n).
Final Points:
 The flow returned by FordFulkersen Algorithm is a maximum flow.
 Our time analysis assumes that the capacities are integers.
 Given a flow of maximum value, we can compute st cut of minimum capacity in O(m) time.
 In every flow network, the maximum value of st flow is equal to the minimum capacity of st cut.
 Dinic’s algorithm computes Max Flow in O(n^{2}m).
Advertisements