Encyclopedia > Max flow min cut theorem

  Article Content

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Canadian Charter of Rights and Freedoms

... and provincial legislatures in Canada when it was adopted by the British Parliament in 1982 (though as part of the Canada Act (UK) 1982 it only became law in Canada, no ...

 
 
 
This page was created in 41.6 ms