MAXIMAL FLOW THROUGH A NETWORK
L. R. FORD, JR. AND D. R. FULKERSON
Introduction. The problem discussed in this paper was formulated by
T. Harris as follows:
"Consider a rail network connecting two cities by way of a number of
intermediate cities, where each link of the network has a number assigned to
it representing its capacity. Assuming a steady state condition, find a maximal
flow from one given city to the other."
While this can be set up as a linear programming problem with as many
equations as there are cities in the network, and hence can be solved by the
simplex method (1), it turns out that in the cases of most practical interest,
where the network is planar in a certain restricted sense, a much simpler and
more efficient hand computing procedure can be described.
In §1 we prove the minimal cut theorem, which establishes that an obvious
upper bound for flows over an arbitrary network can always be achieved.
The proof is non-constructive. However, by specializing the network (§2),
we obtain as a consequence of the minimal cut theorem an effective computational
scheme. Finally, we observe in §3 the duality between the capacity
problem and that of finding the shortest path, via a network, between two
given points.
1. The minimal cut theorem. A graph G is a finite, 1-dimensional
complex, composed of vertices a, b, c, . . . , e, and arcs a(ab), P(ac), . . . , 8(ce).
An arc a(ab) joins its end vertices a, b; it passes through no other vertices of G
and intersects other arcs only in vertices. A chain is a set of distinct arcs of
G which can be arranged as a(ab), ft (be), y(cd), . . . , ô(gh), where the vertices
a, by c, . . . , h are distinct, i.e., a chain does not intersect itself; a chain joins
its end vertices a and h.
We distinguish two vertices of G: a, the source, and b, the sink.1
A chain flow
from a to b is a couple (C; k) composed of a chain C joining a and b, and a
non-negative number k representing the flow along C from source to sink.
Each arc in G has associated with it a positive number called its capacity.
We call the graph G, together with the capacities of its individual arcs, a
network. A flow in a network is a collection of chain flows which has the property
that the sum of the numbers of all chain flows that contain any arc is
no greater than the capacity of that arc. If equality holds, we say the arc is
saturated by the flow. A chain is saturated with respect to a flow if it contains
Received September 20, 1955.
xThe case in which there are many sources and sinks with shipment permitted from any
source to any sink is obviously reducible to this.
399 400 L. R. FORD, JR. AND D. R. FULKERSON
a saturated arc. Th e value of a flow is the sum of the numbers of all the chain
flows which compose it.
It is clear tha t the above definition of flow is not broad enough to include