Page 285 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes an edge (v; u) with capacity x in the residual graph. Figure 14.4 shows the residual graph after
fi nding our fi rst path:
Figure 14.4: The Dashed Edges are the Edges we added in the Residual Graph

a

3/4
0/2

s 3/3 t

3/4
0/2

s

The capacity of the dashed edge is the same as the amount of water carried by the solid edge in
the opposite direction.

So here is an algorithm to find the maximum flow: First construct the residual graph (in the
beginning, the residual graph is the same as the network graph). While there exists a path from s
to t in the residual graph, we flow water through one of the path (a path in the a residual graph

is called an augmenting path). We then adjust the residual graph accordingly. Once we can no

longer find any more path in the residual graph, we have found the maximum fl ow.
14.1.2 Comparison Networks

Suppose we have a directed network G = (V, E) defined by a set V of nodes (or vertexes) and

a set E of arcs (or edges). Each arc (i,j) in E has an associated nonnegative capacity u . Also we
ij
distinguish two special nodes in G: a source node s and a sink node t. For each i in V we denote by
E(i) all the arcs emanating from node i. Let U = max u by (i,j) in E. Let us also denote the number
ij
of vertexes by n and the number of edges by m.

We wish to find the maximum flow from the source node s to the sink node t that satisfies the arc

capacities and mass balance constraints at all nodes. Representing the flow on arc (i,j) in E by x
ij
we can obtain the optimization model for the maximum fl ow problem:
Maximize f(x) = ∑ x ij
ij
∈
(, ) E ( ) s
subject to
∑ x ij – ∑ x ij = 0 ∀i ∈ V\{s, t}
j j
(:( , ) j ∈ } E {:( , ) i ∈ } E
j i
0 ≤ x ≤ u (i, j) ∀(i, j) ∈ E
ij ij
Vector (x ) which satisfi es all constraints is called a feasible solution or, a fl ow (it is not necessary
ij
maximal). Given a fl ow x we are able to construct the residual network with respect to this fl ow
according to the following intuitive idea. Suppose that an edge (i,j) in E carries x units of fl ow.
ij
We define the residual capacity of the edge (i,j) as r = u - x . This means that we can send an

ij
ij
ij
additional r units of flow from vertex i to vertex j. We can also cancel the existing fl ow x on the

ij ij
arc if we send up x units of fl ow from j to i over the arc (i,j).
ij
So, given a feasible fl ow x we define the residual network with respect to the fl ow x as follows.

Suppose we have a network G = (V, E). A feasible solution x engenders a new (residual) network,
280 LOVELY PROFESSIONAL UNIVERSITY