Maximum Flow, Minimum Cut Theorem

The maximum flow between vertices v_i and v_j in a graph G is exactly the weight of the smallest set of edges to disconnect G with v_i and v_j in different components (Ford and Fulkerson 1962; Skiena 1990, p. 178).

See also

Network Flow

Explore with Wolfram|Alpha


Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Maximum Flow, Minimum Cut Theorem

Cite this as:

Weisstein, Eric W. "Maximum Flow, Minimum Cut Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications