Suppose G is a finite directed graph and every edge e has a capacity w(e), a nonnegative 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
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
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:
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 FordFulkerson algorithm.
Search Encyclopedia

Featured Article
