Max-flow min-cut theorem
The max-flow min-cut theorem is a fundamental result in graph theory and network optimization that establishes an equivalence between the maximum flow value in a capacitated flow network and the minimum capacity of a cut separating the source from the sink.[1] In precise terms, for a flow network with source vertex s and sink vertex t, the theorem states that the value of the maximum s-t flow equals the capacity of the minimum s-t cut, where a cut is a partition of the vertices into sets S and T with s in S and t in T, and its capacity is the sum of the capacities of edges from S to T.[2] This duality provides a powerful min-max relation that underpins algorithms for computing maximum flows, such as the Ford-Fulkerson method.[3] The theorem was independently discovered and proved by Lester R. Ford Jr. and Delbert R. Fulkerson in their seminal 1956 paper "Maximal Flow Through a Network," where they introduced the augmenting path approach to demonstrate that the maximum flow equals the minimum cut capacity over all possible cuts.[4] Their work built on earlier ideas in operations research and transportation problems, formalizing the connection between flow conservation and cut capacities through a constructive proof that guarantees the equality.[4] This result not only resolved a key problem in linear programming duality for networks but also highlighted the integrality of flows when capacities are integers, enabling polynomial-time algorithms like Edmonds-Karp.[5] Beyond its theoretical elegance, the max-flow min-cut theorem has profound applications across computer science and mathematics, including finding maximum matchings in bipartite graphs, determining vertex-disjoint paths in directed graphs, and solving combinatorial optimization problems such as image segmentation and airline scheduling.[6] It also extends to multicommodity flows, where multiple sources and sinks are considered, yielding theorems used in network design, routing protocols, and approximating cuts in large-scale graphs.[7] In operations research, the theorem facilitates modeling real-world constraints like transportation bottlenecks, ensuring optimal resource allocation while respecting capacity limits.[8]Definitions and Statement
Flow Network
A flow network is formally defined as a directed graph G = (V, E), where V is the set of vertices and E is the set of directed edges.[9] Two distinguished vertices are identified: a source s \in V, from which flow originates, and a sink t \in V, at which flow terminates.[10] Each edge e \in E is assigned a capacity c(e), given by a function c: E \to \mathbb{R}_{\geq 0}, which specifies the maximum amount of flow that can traverse that edge.[11] These capacities are non-negative real numbers, ensuring that the network models physical or abstract constraints on resource transmission.[9] In some formulations, capacities may be infinite for certain edges, indicating no upper bound on the flow through them; such cases are handled by treating infinite capacities as sufficiently large values in algorithms or by noting their implication for unbounded flows.[12] Undirected networks arise as special cases and are typically converted to directed graphs by replacing each undirected edge between vertices u and v with two directed edges (u, v) and (v, u), each assigned the same capacity.[13] This graph-theoretic structure provides the essential model for analyzing flow assignments and partitions in the max-flow min-cut theorem.[9]Flows
In a flow network G = (V, E) with source s, sink t, and capacity function c: E \to \mathbb{R}_{\geq 0}, a flow f is a function f: E \to \mathbb{R}_{\geq 0} that assigns a non-negative real value to each edge, representing the rate of flow along that edge.[11][10] This flow must satisfy the capacity constraint: for every edge e \in E, $0 \leq f(e) \leq c(e), ensuring no edge carries more flow than its specified capacity.[11][10] Additionally, the conservation of flow holds: for every vertex v \in V \setminus \{s, t\}, the total incoming flow equals the total outgoing flow, given by \sum_{u: (u,v) \in E} f(u,v) = \sum_{w: (v,w) \in E} f(v,w), where the net flow into or out of intermediate vertices is zero.[11][10] The value of a flow f, denoted |f| or \mathrm{val}(f), measures its total throughput and is defined as the net flow leaving the source: |f| = \sum_{w: (s,w) \in E} f(s,w) - \sum_{u: (u,s) \in E} f(u,s).[11][10] By the conservation law, this value equals the net flow entering the sink. The maximum flow problem is to find a feasible flow f^* that maximizes |f| while satisfying the capacity and conservation constraints.[11][10] Solution approaches typically introduce the residual network, which tracks remaining capacities to enable incremental improvements to the flow without violating constraints.[11][10]Cuts
In a flow network G = (V, E) with source s and sink t, an s-t cut (S, T) is a partition of the vertex set V into two disjoint subsets S and T such that s \in S, t \in T, S \cup T = V, and S \cap T = \emptyset.[14] The edges in E can then be classified relative to the cut: forward edges are those directed from a vertex in S to a vertex in T, while backward edges are those directed from T to S.[15] The capacity of an s-t cut (S, T), denoted \delta(S), is the sum of the capacities of the forward edges crossing the cut, ignoring the capacities of backward edges: \delta(S) = \sum_{\substack{(u,v) \in E \\ u \in S, v \in T}} c(u,v). [16] The minimum cut problem seeks to find a partition (S^*, T^*) that minimizes \delta(S) over all possible s-t cuts.[17] For any feasible flow f in the network and any s-t cut (S, T), the value of the flow |f| satisfies |f| \leq \delta(S), with equality holding if and only if every forward edge across the cut is saturated (i.e., f(u,v) = c(u,v) for all forward edges (u,v)) and there is zero flow on every backward edge across the cut (i.e., f(v,u) = 0 for all backward edges (v,u)).[14] This inequality arises because the net flow across the cut cannot exceed the total capacity of the forward edges, as flow conservation ensures that the outflow from S (or inflow to T) equals |f|.[15] Cuts represent potential bottlenecks in the network, as the maximum possible flow from s to t is fundamentally limited by the smallest such cut capacity.[18]The Theorem
The max-flow min-cut theorem asserts that, in any flow network G = (V, E) with source vertex s and sink vertex t, and non-negative finite capacities c: E \to \mathbb{R}_{\geq 0}, the maximum value of an s-t flow equals the minimum capacity of an s-t cut.[4][11] Formally, letting \mathcal{F} denote the set of all valid s-t flows and \mathcal{C} the set of all s-t cuts, the theorem states \max_{f \in \mathcal{F}} |f| = \min_{(S, T) \in \mathcal{C}} \delta(S), where |f| is the value of flow f (net flow out of s), and \delta(S) is the capacity of the cut (S, T) with s \in S and t \in T.[4][11] This equality holds under the standard assumptions of conservation of flow at non-source/sink vertices and non-negativity of flows bounded by capacities.[11] If all capacities c(e) are integers, then the maximum flow value is an integer, and there exists a maximum flow f such that f(e) is an integer for every edge e \in E.[11] The theorem's key implication is that it furnishes a combinatorial certificate for the optimality of any maximum flow: a minimum cut provides explicit proof that no greater flow value is achievable, enabling efficient verification without exhaustive search over all flows.[11] More broadly, the duality between flows and cuts allows reformulating flow maximization problems as cut minimization tasks, which often simplifies theoretical analysis and algorithmic approaches.[19]Examples and Formulations
Illustrative Example
Consider a simple flow network with four vertices: a source s, intermediate vertices a and b, and a sink t. The directed edges and their capacities are as follows: s \to a with capacity 3, s \to b with capacity 2, a \to b with capacity 1, a \to t with capacity 2, and b \to t with capacity 2.[4] To compute the maximum flow using the Ford-Fulkerson algorithm, begin with zero flow and identify augmenting paths in the residual graph.[4] The first augmenting path is s \to a \to t, with bottleneck capacity \min(3, 2) = 2; augment the flow by 2 along this path. The updated residual capacities are s \to a: 1, a \to t: 0, and reverse edges a \to s: 2, t \to a: 2. The current flow value is 2. The next augmenting path is s \to b \to t, with bottleneck capacity \min(2, 2) = 2; augment by 2. The updated residual capacities are s \to b: 0, b \to t: 0, and reverse edges b \to s: 2, t \to b: 2. The flow value is now 4. No further augmenting paths exist from s to t in the residual graph, as a \to t and b \to t are saturated, and the path s \to a \to b \to t is blocked by the zero residual capacity on b \to t. Thus, the maximum flow f^* has value |f^*| = 4.[4] The flow assignments on the edges are summarized in the following table:| Edge | Flow | Capacity |
|---|---|---|
| s \to a | 2 | 3 |
| s \to b | 2 | 2 |
| a \to b | 0 | 1 |
| a \to t | 2 | 2 |
| b \to t | 2 | 2 |