Max-flow min-cut theorem
Maximum flow equals minimum cut capacity in a network.
The max-flow min-cut theorem is a key idea in computer science and optimization theory. It says that in a flow network, the largest possible flow from the source to the sink equals the smallest total capacity of a set of edges whose removal would separate the source from the sink. This smallest total capacity is called the minimum cut. For instance, picture a water pipe network connecting a reservoir (the source) to a city (the sink). Each pipe has a capacity, the maximum water it can carry per unit time. The theorem shows that the maximum water reaching the city is limited by the smallest combined capacity of any group of pipes that, if cut, would completely isolate the reservoir from the city. That bottleneck, the min-cut, determines the overall maximum flow. The theorem is a special instance of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem.
To state the theorem precisely, we first define the two quantities it equates: the maximum flow through a network and the minimum capacity of a cut.
A network consists of a finite directed graph G = (V, E), where V is the set of vertices and E is the set of directed edges; a source s and a sink t, both in V; and a capacity function c: E → ℝ⁺, written as c(u,v) for edge (u,v), which gives the maximum flow that edge can carry.
A flow through the network is a function f: E → ℝ⁺, written as f(u,v), that obeys two rules. First, the capacity constraint: for every edge (u,v), f(u,v) ≤ c(u,v). Second, the conservation of flows: for every vertex v except s and t, the total flow into v equals the total flow out of v. This is like a physical fluid flowing through the network along the edges: each edge’s flow rate cannot exceed its capacity, and at any vertex that is not the source or sink, the amount of fluid entering equals the amount leaving. The value of a flow, |f|, is the total flow leaving the source (which, by conservation, equals the total flow entering the sink). The maximum flow problem asks for the largest possible |f| on a given network.
- 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 1-24
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