Max-flow min-cut theorem

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the 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 duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.

The theorem equates two quantities: the maximum flow through a network, and the minimum capacity of a cut of the network. To state the theorem, each of these notions must first be defined.

A network consists of

A flow through a network is a mapping ${\displaystyle f:E\to \mathbb {R} ^{+}}$ denoted by ${\displaystyle f_{uv}}$ or ${\displaystyle f(u,v)}$, subject to the following two constraints:

A flow can be visualized as a physical flow of a fluid through the network, following the direction of each edge. The capacity constraint then says that the volume flowing through each edge per unit time is less than or equal to the maximum capacity of the edge, and the conservation constraint says that the amount that flows into each vertex equals the amount flowing out of each vertex, apart from the source and sink vertices.

The value of a flow is defined by