Maximum Flow1

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

Capacity constraint - For all u, v Î V, f (u, v) £ c (u, v) i.e., the net flow from one vertex to the other must not exceed the given capacity
Skew symmetry - For all u, v Î V, f (u, v) = -f (v, u), i.e., the net flow from vertex u to vertex v is the negative of the net flow in the reverse direction
Flow conservation - For all u Î V- {s, t}, S _vÎ V f (u, v) = 0, i.e., the total net flow out of a vertex other than the source or sink is 0

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

This method is iterative and is started with flow between all vertices belonging to V initialized to 0.
At each iteration, the flow value is increased by finding an "augmenting path" which is a path between the source and the sink along which more flow can be pushed and then augmenting the flow along this path.
This process is repeated until no augmenting path is found.

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

C_f(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, E_f) where E_f = {(u, v) Î V X V : c_f (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 G_f. 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

C_f(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 G_f

do c_f(p) = min { c_f (u, v) : (u, v) is in p}

for each edge (u, v) in p

do f[u, v] = f[u, v] + c_f(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(VE²) 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