Editing Max-flow min-cut theorem (section)

{{short description|Concept in optimization theory}}
In [[computer science]] and [[Optimization (mathematics)|optimization theory]], the '''max-flow min-cut theorem''' states that in a [[flow network]], the maximum amount of flow passing from the [[Glossary of graph theory#Direction|''source'']] to the [[Glossary of graph theory#Direction|''sink'']] is equal to the total weight of the edges in a [[minimum cut]], i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

For example, imagine a network of pipes carrying water from a reservoir (the source) to a city (the sink). Each pipe has a capacity representing the maximum amount of water that can flow through it per unit of time. The max-flow min-cut theorem tells us that the maximum amount of water that can reach the city is limited by the smallest total capacity of any set of pipes that, if cut, would completely isolate the reservoir from the city. This smallest total capacity is the min-cut. So, if there's a bottleneck in the pipe network, represented by a small min-cut, that bottleneck will determine the overall maximum flow of water to the city.

This is a special case of the [[dual problem|duality theorem]] for [[linear program]]s and can be used to derive [[Menger's theorem]] and the [[Kőnig's theorem (graph theory)|Kőnig–Egerváry theorem]].<ref>{{cite journal| last1=Dantzig |first1=G.B. |last2= Fulkerson |first2=D.R.|title=On the max-flow min-cut theorem of networks|journal=RAND Corporation|date=9 September 1964| page=13 |url= http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|archive-url=https://web.archive.org/web/20180505093256/http://www.dtic.mil/dtic/tr/fulltext/u2/605014.pdf|archive-date=5 May 2018|url-status=dead}}</ref>