maxflowmincut

In graph theory, the max-flow min-cut theorem, commonly called the max-flow min-cut theorem, relates the maximum feasible flow from a source to a sink to the minimum total capacity of a cut that separates them. It applies to directed graphs with nonnegative edge capacities.

A flow network is a directed graph G = (V,E) with a source s ∈ V and a sink t ∈ V, together with a capacity function c: E → R+. A flow f assigns to each edge (u,v) a value 0 ≤ f(u,v) ≤ c(u,v) and must satisfy flow conservation: for every vertex v ≠ s,t, the sum of incoming flows equals the sum of outgoing flows. The flow's value is |f|, the net flow out of s.

An s-t cut partitions V into S and T with s ∈ S, t ∈ T. The cut's capacity is the sum of c(u,v) for edges from S to T. The cut measures the total capacity that must cross the boundary from S to T.

The max-flow min-cut theorem states that the maximum possible value of an s-t flow equals the minimum capacity among all s-t cuts. Equivalently, when no augmenting path exists in the residual graph, the current flow is maximum and the corresponding cut has capacity equal to the flow value.

The theorem is proved using the concept of residual networks and augmenting paths; its constructive proofs lead to algorithms for computing max flows, such as Ford-Fulkerson, Edmonds-Karp, Dinic, and push-relabel methods. It underpins many applications where bottlenecks determine feasibility, including network design, bipartite matching, and image segmentation.

Variants include undirected networks and multiple sources or sinks, which can be reduced to the standard single-source single-sink problem. For networks with integral capacities, the max flow value is integral as well, enabling exact combinatorial interpretations.