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 fin(v)) equals total +ve flow going out of v (or fout(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(V-s,V)
= f(V,V-s)
= f(V,t) + f(V,V-s-t)
= f(V,t) – f(V-s-t,V)
= f(V,t)
The Maximum-Flow 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, cf(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 Gf, 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.
fp(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)+fp(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,V-S)
- = f(S,V)
- = f(s,V) + f(V-s,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,
-
- Gf has no augmenting path
-
- Proof:
-
- |f’| = |f| + |fp| 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 V-S.
- As there are no outgoing edges from S to T in Gf , f(S,T) must be equal to c(S,T).
Ford-Fulkerson Algorithm for finding Max-Flow:
Max-Flow
Initially f(e)=0 for all e in GWhile there is an s-t path in the residual graph Gf
- Let P be any (not necessarily simple, simple makes it the generic flow algorithm) s-t path in Gf
- f’= augment(f, P)
- Update f to be f’
- Update the residual graph Gf to be Gf’
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 s-t path cost as all other points conserved
- At most |F| iterations where |F| is maximum flow.
- Hence running time at most O(m|F|) as BFS in O(m+n) and n<=2*m as all nodes have at least one incident edge.
Edmond-Karp Algorithm for finding Max-Flow:
Same as the Generic flow algorithm, with augmentation done only with shortest BFS paths (edge weights as 1).
Running Time With This Modification: O(m2n).
Proof that running time is O(m2n):
- 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 Li to Li+1 was removed, Li+1 to Li 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(m2n).
Final Points:
- The flow returned by Ford-Fulkersen Algorithm is a maximum flow.
- Our time analysis assumes that the capacities are integers.
- Given a flow of maximum value, we can compute s-t cut of minimum capacity in O(m) time.
- In every flow network, the maximum value of s-t flow is equal to the minimum capacity of s-t cut.
- Dinic’s algorithm computes Max Flow in O(n2m).
Advertisements