Max-flow min-cut theorem
Maximum flow equals minimum cut capacity in a network.
Last updated
This result is an instance of the linear programming duality theorem.[1]
Quick Facts
- Field
- Computer science, optimization theory
- Type
- Theorem
- Related theorems
- Menger's theorem, Kőnig–Egerváry theorem
Facts from the source article.
Key facts and history
The problem was posed to Ford and Fulkerson in the spring of 1955 by T.E. Harris.[2] Harris, in conjunction with General F. S. Ross, had formulated a simplified model of railway traffic flow.[2] The central problem suggested by that model was determining a maximal steady state flow subject to arc capacity limitations.[2] A number of proofs have since appeared.[2]
The constraints guarantee that the variables indeed represent a legal cut.[3] Theorem 5.1, now called the max-flow min-cut theorem, was first hypothesized and then proven shortly after the problem was posed.[2]
What the research sources say
Ford and Fulkerson gave an account of the discovery of the theorem in 1962.[4] In that model, as the input voltage tends toward infinity, the current's limiting value equals the weight of the minimum-weight cut set.[5]
References
- Wikipedia, "Max-flow min-cut theorem" (CC BY-SA 4.0), which cites: Dantzig, "On the max-flow min-cut theorem of networks", RAND Corporation, 9 September 1964, p. 13 (original not read by us) en.wikipedia.org
- Wikipedia, "Max-flow min-cut theorem" (CC BY-SA 4.0), which cites: L. R. Ford Jr. and D. R. Fulkerson (1956) "Maximal flow through a network", Canadian Journal of Mathematics 8: 399–404; P. Elias, A. Feinstein, and C. E. Shannon (1956) "A note on the maximum flow through a network", IRE. Transactions on Information Theory, 2(4): 117–119; George Dantzig and D. R. Fulkerson (1956) "On the Max-Flow MinCut Theorem of Networks", in Linear Inequalities, Ann. Math. Studies, no. 38, Princeton, New Jerse; L. R. Ford & D. R. Fulkerson (1957) "A simple algorithm for finding the maximum network flows and en.wikipedia.org
- Wikipedia, "Max-flow min-cut theorem" (CC BY-SA 4.0), which cites: Keller, "LP min-cut max-flow presentation" (original not read by us) en.wikipedia.org
- Wikipedia, "Max-flow min-cut theorem" (CC BY-SA 4.0), which cites: L. R. Ford Jr. & D. R. Fulkerson (1962) Flows in Networks, page 1, Princeton University Press (original not read by us) en.wikipedia.org
- Wikipedia, "Max-flow min-cut theorem" (CC BY-SA 4.0), which cites: Cederbaum, "On the optimal operation of communication nets", Journal of the Franklin Institute, August 1962, p. 130–141 (original not read by us) en.wikipedia.org
Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Max-flow min-cut theorem (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.
More in Algorithms And Data Structures
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Max-flow min-cut theorem (CC BY-SA 4.0).
- Word definitions: the Codexery glossary, each quoted from its Wikipedia article.
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced