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.
Definitions and statement 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.
Network A network consists of
a finite directed graph G = (V, E), where V denotes the finite set of vertices and E ⊆ V×V is the set of directed edges; a source s ∈ V and a sink t ∈ V; a capacity function, which is a mapping c : E → R + {\displaystyle c:E\to \mathbb {R} ^{+}} denoted by cuv or c(u, v) for (u,v) ∈ E. It represents the maximum amount of flow that can pass through an edge.
Flows A flow through a network is a mapping f : E → R + {\displaystyle f:E\to \mathbb {R} ^{+}} denoted by f u v {\displaystyle f_{uv}} or f ( u , v ) {\displaystyle f(u,v)} , subject to the following two constraints:
Capacity Constraint: For every edge ( u , v ) ∈ E {\displaystyle (u,v)\in E} , f u v ≤ c u v . {\displaystyle f_{uv}\leq c_{uv}.}
Conservation of Flows: For each vertex v {\displaystyle v} apart from s {\displaystyle s} and t {\displaystyle t} (i.e. the source and sink, respectively), the following equality holds: ∑ { u : ( u , v ) ∈ E } f u v = ∑ { w : ( v , w ) ∈ E } f v w . {\displaystyle \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.}
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
| f | = ∑ { v : ( s , v ) ∈ E } f s v = ∑ { v : ( v , t ) ∈ E } f v t , {\displaystyle |f|=\sum \nolimits _{\{v:(s,v)\in E\}}f_{sv}=\sum \nolimits _{\{v:(v,t)\in E\}}f_{vt},}
where as above s {\displaystyle s} is the source and t {\displaystyle t} is the sink of the network. In the fluid analogy, it represents the amount of fluid entering the network at the source. Because of the conservation axiom for flows, this is the same as the amount of flow leaving the network at the sink. The maximum flow problem asks for the largest flow on a given network.
Maximum Flow Problem. Maximize | f | {\displaystyle |f|} , that is, to route as much flow as possible from s {\displaystyle s} to t {\displaystyle t} .
… excerpt ends here. Continue reading the full article.
