Max flow min cut theorem

The max flow min cut theorem is a statement in optimization theory about optimal flows in networks.

Suppose G is a finite directed graph and every edge e has a capacity w(e), a non-negative real number. Further assume two vertices s and t have been distinguished. Think of G as a network of pipes; we want to pump as much stuff as possible from the source s to the sink t, never exceeding any edge's capacity.

A flow f on G from s to t assigns to each edge e a real number f(e) with 0 ≤ f(e) ≤ w(e) such that for every vertex x of G different from s and t, we have

<math>

\sum_{e \; \in \; I(x)} f(e) = \sum_{e \; \in \; O(x)} f(e) </math>

where I(x) is the set of all incoming edges of x and O(x) is the set of all outgoing edges of x ("whatever goes in must come out"). For such a flow, we automatically have

<math>

\sum_{e \; \in \; O(s)} f(e) \; - \sum_{e \; \in \; I(s)} f(e) \quad = \quad \sum_{e \; \in \; I(t)} f(e) \; - \sum_{e \; \in \; O(t)} f(e) </math>

this number is called the amount of the flow. Intuitively, it is the net total amount of stuff we are pumping from s to t. We are interested in flows with maximal amount.

A cut C on G between s and t is a set of edges such that every directed path from s to t passes through at least one edge in C. The capacity of the cut C is the sum of all its edge capacities.

The statement of the theorem is:

The maximal amount of a flow is equal to the minimal capacity of a cut.

Note that there may be several flows which attain the maximum amount, and there may be several cuts which attain the minimal weight.

There is a partial correspondence between maximal flows and minimal cuts: if C is a minimal capacity cut, then there exists at least one maximal value flow f such that f(e) = w(e) for all e in C. Conversely, if f is a maximal flow, then there is a minimal cut C such that f(e) = w(e) for all e in C.

The theorem was proved by A. Feinstein and C.E. Shannon in 1956, and independently also by L.R. Ford, Jr. and D.R. Fulkerson in the same year. Determining maximum flows is a special kind of linear programming problem, and the max flow min cut theorem can be seen as a special case of the duality theorem for linear programming.

Maximum flows can be computed with the Ford-Fulkerson algorithm.