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 capacity of a minimal 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 method, which is most commonly implemented according to the Edmonds-Karp algorithm. This implies that the maximum flow of a graph with integer capacities has an integer value as well. Another way to prove this is to notice that one of the linear programming formulations of the max flow problem has a totally unimodular constraint matrix, and so has integer solutions.
External link
A review of current literature on computing maximum flows (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE167.HTM)