In this section, we consider the important problem of maximizing the flow of a ma-terial through a transportation network (pipeline system, communication system, electrical distribution system, and so on).

**The Maximum-Flow Problem**

In this section, we consider
the important problem of maximizing the flow of a ma-terial through a
transportation network (pipeline system, communication system, electrical
distribution system, and so on). We will assume that the transportation network
in question can be represented by a connected weighted digraph with ** n** vertices numbered from 1 to

It contains exactly one
vertex with no entering edges; this vertex is called the ** source **and assumed to be
numbered 1.

It contains exactly one vertex
with no leaving edges; this vertex is called the ** sink **and assumed to be
numbered

The weight *u***_{ij}** of each directed edge

A digraph satisfying these
properties is called a ** flow network** or simply a

It is assumed that the source
and the sink are the only source and destination of the material, respectively;
all the other vertices can serve only as points where a flow can be redirected
without consuming or adding any amount of the material. In other words, the
total amount of the material entering an intermediate vertex must be equal to
the total amount of the material leaving the vertex. This con-dition is called
the ** flow-conservation
requirement**. If we denote the amount sent through edge

where the sums in the left-
and right-hand sides express the total inflow and outflow entering and leaving
vertex ** i,** respectively.

Since no amount of the
material can change by going through intermediate vertices of the network, it
stands to reason that the total amount of the material leaving the source must
end up at the sink. (This observation can also be derived formally from
equalities (10.8), a task you will be asked to do in the exercises.) Thus, we
have the following equality:

This quantity, the total
outflow from the source—or, equivalently, the total inflow into the sink—is
called the ** value** of the flow. We denote it by

Thus, a (feasible) ** flow**
is an assignment of real numbers

The ** maximum-flow problem** can
be stated formally as the following optimization problem:

We can solve linear
programming problem (10.11) by the simplex method or by another algorithm for
general linear programming problems (see Section 10.1). However, the special
structure of problem (10.11) can be exploited to design faster algorithms. In particular,
it is quite natural to employ the iterative-improvement idea as follows. We can
always start with the zero flow (i.e., set *x***_{ij}** = 0 for every edge

An actual implementation of
the augmenting path idea is, however, not quite straightforward. To see this,
let us consider the network in Figure 10.4. We start with the zero flow shown
in Figure 10.5a. (In that figure, the zero amounts sent through each edge are
separated from the edge capacities by the slashes; we will use this notation in
the other examples as well.) It is natural to search for a flow-augmenting path
from source to sink by following directed edges ** (i, j )** for which the current flow

Thus, to find a
flow-augmenting path for a flow ** x,** we need to consider paths
from source to sink in the underlying

connected by a directed edge from ** i** to

connected by a directed edge from ** j** to

Edges of the first kind are
called ** forward edges** because their tail is listed before their head in
the vertex list 1 →

For a given flow-augmenting
path, let ** r** be the minimum of all the
unused capacities

flow whose value is ** r** units greater than the value of its
predecessor. Indeed, let

For each of them, the
flow-conservation requirement for vertex ** i** will still hold after the flow adjustments
indicated above the edge arrows. Further, since

Under the assumption that all
the edge capacities are integers, ** r** will be a positive integer
too. Hence, the flow value increases at least by 1 on each iteration of the
augmenting-path method. Since the value of a maximum flow is bounded above
(e.g., by the sum of the capacities of the source edges), the augmenting-path
method has to stop after a finite number of iterations.

The augmenting-path method—as
described above in its general form—does not indicate a specific way for
generating flow-augmenting paths. A bad sequence of such paths may, however,
have a dramatic impact on the method’s efficiency. Consider, for example, the
network in Figure 10.6a, in which ** U** stands for some large
positive integer. If we augment the zero flow along the path 1→2→3→4, we shall obtain the flow of value 1 shown in
Figure 10.6b. Augmenting that flow along the path 1→3←2→4 will increase the flow value to 2 (Figure
10.6c). If we continue selecting this pair of flow-augmenting paths, we will
need a total of 2

Fortunately, there are
several ways to generate flow-augmenting paths ef-ficiently and avoid the
degradation in performance illustrated by the previous example. The simplest of
them uses breadth-first search to generate augment-ing paths with the least
number of edges (see Section 3.5). This version of the augmenting-path method,
called ** shortest-augmenting-path** or

If unlabeled vertex ** j** is connected to the front vertex

vertex ** j** is labeled with

If unlabeled vertex ** j** is connected to the front vertex

*l*_{j}* , i*^{−}** , **where

If this labeling-enhanced
traversal ends up labeling the sink, the current flow can be augmented by the
amount indicated by the sink’s first label. The augmentation is performed along
the augmenting path traced by following the vertex second labels from sink to
source: the current flow quantities are increased on the forward edges and
decreased on the backward edges of this path. If, on the other hand, the sink
remains unlabeled after the traversal queue becomes empty, the algorithm
returns the current flow as maximum and stops.

**ALGORITHM** *ShortestAugmentingPath(G)*

//Implements the
shortest-augmenting-path algorithm //Input: A network with single source 1,
single sink ** n**, and // positive integer
capacities

assign *x***_{ij}** = 0 to every edge

label the source with ∞** ,** − and add the source to the empty queue

capacities of the edges that
compose the cut. For the three examples of cuts given above, the capacities are
equal to 5, 6, and 9, respectively. Since the number of different cuts in a
network is nonempty and finite (why?), there always exists a ** minimum
cut**, i.e., a cut with the smallest capacity. (What is a minimum cut in
the network of Figure 10.4?) The following theorem establishes an important
relationship between the notions of maximum flow and minimum cut.

**THEOREM
( Max-Flow Min-Cut Theorem) **The value of a maximum flow
in a

Thus, the value of any
feasible flow in a network cannot exceed the capacity of any cut in that
network.

Let *v*^{∗} be the value of a final flow *x*^{∗} obtained by the augmenting-path method. If we
now find a cut whose capacity is equal to *v*^{∗}** ,** we will
have to conclude, in view of inequality (10.13), that (i) the value

the maximum-flow value is equal to the minimum-cut capacity.

To find
such a cut, consider the set of vertices *X*^{∗} that
can be reached from the

source by following an
undirected path composed of forward edges with positive unused capacities (with
respect to the final flow *x*^{∗}) and backward edges with positive flows on
them. This set contains the source but does not contain the sink: if it did, we
would have an augmenting path for the flow *x*^{∗}, which would

The proof outlined above
accomplishes more than proving the equality of the maximum-flow value and the
minimum-cut capacity. It also implies that when the augmenting-path method
terminates, it yields both a maximum flow and a mini-mum cut. If labeling of
the kind utilized in the shortest-augmenting-path algorithm is used, a minimum
cut is formed by the edges from the labeled to unlabeled ver-tices on the last
iteration of the method. Finally, the proof implies that all such edges must be
full (i.e., the flows must be equal to the edge capacities), and all the edges
from unlabeled vertices to labeled, if any, must be empty (i.e., have zero
flows on them). In particular, for the network in Figure 10.7, the algorithm
finds the cut {** (**1

Edmonds and Karp proved in
their paper [Edm72] that the number of aug-menting paths needed by the
shortest-augmenting-path algorithm never exceeds ** nm/**2

More efficient algorithms for
the maximum-flow problem are known (see the monograph [Ahu93], as well as
appropriate chapters in such books as [Cor09] and [Kle06]). Some of them
implement the augmenting-path idea in a more efficient manner. Others are based
on the concept of preflows. A ** preflow** is a flow that satisfies the
capacity constraints but not the flow-conservation requirement. Any vertex is
allowed to have more flow entering the vertex than leaving it. A preflow-push
algorithm moves the excess flow toward the sink until the flow-conservation
requirement is reestablished for all intermediate vertices of the network.
Faster al-gorithms of this kind have worst-case efficiency close to

To conclude this section, it
is worth pointing out that although the initial interest in studying network
flows was caused by transportation applications, this model has also proved to
be useful for many other areas. We discuss one of them in the next section.

**Exercises 10.2**

**
**Since maximum-flow algorithms require processing edges in both
directions, it is convenient to modify the adjacency matrix representation of a
network as follows. If there is a directed edge from vertex ** i** to vertex

Apply the shortest-augmenting
path algorithm to find a maximum flow and a minimum cut in the following
networks.

**
****a. **Does the maximum-flow problem
always have a unique solution? Would** **your
answer be different for networks with different capacities on all their edges?

**
**Answer the same questions for the minimum-cut problem of finding a
cut of the smallest capacity in a given network.

**
****a. **Explain how the maximum-flow
problem for a network with several** **sources
and sinks can be transformed into the same problem for a network with a single
source and a single sink.

**
**Some networks have capacity constraints on the flow amounts that
can flow through their intermediate vertices. Explain how the maximum-flow
problem for such a network can be transformed to the maximum-flow problem for a
network with edge capacity constraints only.

**
**Consider a network that is a rooted tree, with the root as its
source, the leaves as its sinks, and all the edges directed along the paths
from the root to the leaves. Design an efficient algorithm for finding a
maximum flow in such a network. What is the time efficiency of your algorithm?

**a. **Prove equality (10.9).

**
**Prove that for any flow in a network and any cut in it, the value
of the flow is equal to the flow across the cut (see equality (10.12)). Explain
the relationship between this property and equality (10.9).

**
****a. **Express the maximum-flow
problem for the network in Figure 10.4 as a**
**linear programming problem.

**
**Solve this linear programming problem by the simplex method.

**
**As an alternative to the shortest-augmenting-path algorithm,
Edmonds and Karp [Edm72] suggested the maximum-capacity-augmenting-path
algorithm, in which a flow is augmented along the path that increases the flow
by the largest amount. Implement both these algorithms in the language of your
choice and perform an empirical investigation of their relative efficiency.

**
**Write a report
on a more
advanced maximum-flow algorithm
such as

(i) Dinitz’s algorithm, (ii)
Karzanov’s algorithm, (iii) Malhotra-Kamar-Maheshwari algorithm, or (iv)
Goldberg-Tarjan algorithm.

**
***Dining problem *Several families go out to
dinner together. To increase their* *social
interaction, they would like to sit at tables so that no two members of the
same family are at the same table. Show how to find a seating arrangement that
meets this objective (or prove that no such arrangement exists) by using a
maximum-flow problem. Assume that the dinner contingent has ** p** families and that the

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Iterative Improvement : The Iterative Maximum-Flow Problem |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.