Max-flow min-cut theorem
Maximum flow equals minimum cut capacity in a network.
The max-flow min-cut theorem is a fundamental result in computer science and optimization theory. It 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. This theorem 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.
- field
- Computer science, optimization theory
- known_for
- Equating maximum flow and minimum cut in a network
- type
- Theorem
- related_theorems
- Menger's theorem, Kőnig–Egerváry theorem
Lore & Background
The theorem equates two quantities: the maximum flow through a network, and the minimum capacity of a cut of the network. A network consists of a finite directed graph with a source and sink, and a capacity function on edges representing the maximum flow that can pass through each edge. A flow is a mapping subject to capacity constraints and conservation of flow at each vertex except source and sink, with the flow value defined as the amount entering the source or leaving the sink.
Reader's Guide
The max-flow min-cut theorem is significant because it provides a precise duality between flow and cut problems in networks. It shows that the maximum flow from source to sink is limited by the smallest total capacity of any set of edges whose removal disconnects source from sink. This result is a special case of the duality theorem for linear programs and serves as a foundation for deriving other important theorems such as Menger's theorem and the Kőnig–Egerváry theorem. The theorem applies to any flow network, where the capacity constraint ensures flow on each edge does not exceed its capacity, and conservation ensures flow into each vertex equals flow out, except at source and sink. The value of any flow is always less than or equal to the capacity of any s-t cut, and a flow with maximal value and a cut with minimal capacity are equal.
Did You Know?
- The theorem states that the maximum flow through a network equals the total weight of edges in a minimum cut.
- A cut is a partition of vertices with source in one part and sink in the other; its capacity is the sum of capacities of edges from source part to sink part.
- The theorem is a special case of the duality theorem for linear programs.
- It can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.
Frequently Asked Questions
Who is Max-flow min-cut theorem?
It is a foundational result in computer science and optimization theory that pins down an exact equality between two quantities in a flow network. In plain terms, it guarantees that the largest possible flow from a source node to a sink node always matches the total capacity of the smallest set of edges whose removal would sever that connection.
What are Max-flow min-cut theorem's powers/role?
Its central role is to certify that no flow can ever exceed the capacity of the minimum cut, and conversely that a flow achieving that bound always exists. This single equality lets engineers and researchers verify optimal routing solutions without enumerating every possible path through the network.
How does Max-flow min-cut theorem connect to other theorems?
It is a special case of the linear-programming duality theorem, so its proof can be lifted directly from that broader principle. It also serves as a stepping stone to Menger's theorem on vertex-disjoint paths and the Kőnig–Egerváry theorem on bipartite matching, making it a hub linking several classic results.
Why is Max-flow min-cut theorem important?
It supplies a provably tight upper bound on any network's throughput, which is essential for designing efficient communication, transportation, and logistics systems. Because the minimum cut gives a certificate of optimality, it underpins countless practical algorithms for routing, scheduling, and resource allocation.
What field does Max-flow min-cut theorem belong to?
It sits at the intersection of computer science and optimization theory, where it anchors the study of network-flow problems. Its statements and proofs draw on graph theory, linear algebra, and combinatorial optimization, effectively bridging several sub-disciplines.
More in Algorithms And Data Structures 25-38
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record