In 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 minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the sink.
The max-flow min-cut theorem is a special case of the duality theorem and can be used to derive Menger's theorem and the König-Egerváry Theorem.
Let N = (V,E) be a network (directed graph) with s and t being the source and the sink of N respectively.
The maximum flow problem is to maximize | f |, that is, to route as much flow as possible from s to the t.
The minimum cut problem is to minimize c(S,T), that is, to determine S and T such that the capacity of the S-T cut is minimal.
The max-flow min-cut theorem states
Linear program formulation
The max-flow problem and min-cut problem can be formulated as two primal-dual linear programs.
The equality in the max-flow min-cut theorem follows from the strong duality theorem, which states that if the primal program has an optimal solution, x*, then the dual program also has an optimal solution, y*, such that the optimal values formed by the two solutions are equal.
Full article ▸