ABSTRACT
A network is a directed graph used to model the distribution of goods, data, or com-
modities, etc., from their centers of production to their destinations. For example,
Figure 10.1 shows a network in which goods are produced at node s, and shipped to node t. Each directed edge has a limited capacity, being the maximum number of goods that can be shipped through that channel per time period (e.g., 3 kilobytes
per second or 3 truckloads per day). The diagram indicates the capacity as a positive
integer associated with each edge. The actual number of goods shipped on each edge
is shown in square brackets beside the capacity. This is called the flow on that edge. It
is a non-negative integer less than or equal to the capacity. Goods cannot accumulate
at any node; therefore, the total in-flow at each node must equal the out-flow at that
node. The problem is to find the distribution of goods that maximizes the net flow
from s to t. This can be modeled mathematically as follows. When the edges of a graph have
a direction, the graph is called a directed graph or digraph. A networkN is a directed graph with two special nodes s and t; s is called the source, and t is called the target. All other vertices are called intermediate vertices. The edges of a directed graph are
ordered pairs (u, v) of vertices, which we denote by −→ uv . We shall find it convenient
to say that u is adjacent to v even when we do not know the direction of the edge. So
the phrase u is adjacent to vmeans either −→ uv or
−→ vu is an edge. Each edge
−→ uv∈ E(N)
has a capacity CAP( −→ uv ), being a positive integer, and a flow f(
−→ uv ), a non-negative
integer, such that f( −→ uv ) ≤ CAP(−→uv ). If v is any vertex of N , the out-flow at v is
f+(v) = ∑
f( −→ vu)
where the sum is over all vertices u to which v is joined. The in-flow is the sum over all incoming edges at v
f−(v) = ∑
f( −→ uv )
A valid flow f must satisfy two conditions.
