Maximum Flow Chapter 27 Lecture Prepared by Aparna Gourisetty
A flow network G = (V, E) is a directed graph in which each edge (u, v) Î E has a non negative capacity
c(u, v) >= 0. If (u, v) Ï E we assume that c (u, v) = 0.
A flow has a source, the starting point and a sink, the end point in its path and it is a real valued function that satisfies the following three properties
The quantity f (u, v) can be positive or negative and is called the net flow from vertex u to vertex v.
The maximum flow problem is the simplest concerning flow networks. It asks " What is the greatest rate at which material can be shipped from the source to the sink without violating any capacity constraints?"
An example of flow network for a source s and a sink t.
A flow f in G with value |f| = 19
Only c (u, v) of material can be transported from u to v. The maximum flow problem can be converted into a transportation problem as in the text. Lucky Puck Company transports hockey pucks from one city to another through various intermediate cities and their goal is to determine the largest number of crates per day p, that can be shipped and to produce this amount since they do not have any place to store the extra pucks produced. This maximum amount can be determined by finding the maximum flow in the network as shown in the figure.
Cancellation:
Exercise 27.1-1:
For any two given vertices u and v having c (u, v) =5 and c (v, u) = 8, suppose if 3 units of flow are shipped from u to v and 4 units from v to u, the net flow from u to v is represented as follows.
The slash is used to separate the flow and capacity
The Ford-Fulkerson method for solving the maximum flow problem
Ford-Fulkerson-Method (G, s, t)
initialize flow f to 0
while there exists an augmenting path p
do augment flow f along p
return f
Residual Networks:
For a given flow network and a flow, the residual network consists of edges that can admit more net flow. The amount of additional net flow that can be pushed from u to v before exceeding the capacity c (u, v) is the residual capacity of (u, v) and is given by
Cf (u, v) = c (u,v) -f (u,v)
Given a flow network G = (V, E) and the flow f, the residual network of G induced by f is G f = (V, Ef) where Ef = {(u, v)
Î V X V : cf (u, v) > 0)}Augmenting paths:
Given a flow network G = (V, E) and a flow f, an augmenting path p is a simple path from s to t in the residual network Gf . The maximum amount of net flow that can be shipped along the edges of an augmenting path p is called the residual capacity of p and is given by
Cf (p) = min {c f (u, v): (u, v) is on p}
Cuts of flow networks:
A cut (S, T) of flow network G = (V, E) is a partition of V into S and T = V - S such that s
Î S and t Î T. If f is the flow, then the net flow across the cut (S, T) is defined to be f (S, T) and the capacity of the cut is c (S, T).The Ford-Fulkerson algorithm
This implementation of the method computes the maximum flow in the graph G = (V, E) by updating the net flow f[u, v] between each pair u, v of vertices that are connected by an edge. If u, v are not connected by an edge, then f[u, v] = 0. It is assumed that the capacity from u to v is provided by a constant-time function c (u, v) with c (u, v) = 0 if (u, v)
Ï E.
Ford-Fulkerson (G, s, t)
for each edge (u, v)
Î E [g]do f [u, v] = 0
f [v, u] = 0
while there exists a path p from s to t in the residual network Gf
do cf (p) = min { cf (u, v) : (u, v) is in p}
for each edge (u, v) in p
do f[u, v] = f[u, v] + cf (p)
f[v, u] = -f [u, v]
The running time of the Ford-Fulkerson algorithm depends on how the augmenting path p is determined.
The bound on the Ford-Fulkerson method can be improved if the augmented path p is found by the breadth first search, i.e., the augmented path is a shortest path from s to t in the residual network where each edge has unit distance (weight). This implementation of the Ford-Fulkerson method is called the Edmonds-Karp algorithm and it runs in O(VE2) time.
Exercise 27.2-2:
Execution of the Edmonds-Karp algorithm on the flow network below.
The first residual graph is the original flow network itself. We need to find the shortest path from s to t. The augmented path using BSF from s would be s, u, v, t.
Augmenting the above path by pushing 12 units of flow along the path (since 12 is the minimum capacity found on the path) we get
The residual graph is
The shortest path is s, x, w, t and its capacity is 4, so pushing 4 units along the path the augmented graph is
The residual path is
The shortest path from s to t using BFS is s, x, w, v, t and its capacity is 7. After pushing 7 units the augmented graph is
And the residual graph is
There are no more shortest paths from s to t. Therefore the maximum flow computed by the Edmond-Karp algorithm is 12 + 4 + 7 = 23