In optimization theory, the maxflow mincut 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 maxflow mincut theorem is a special case of the duality theorem and can be used to derive Menger's theorem and the KönigEgerváry Theorem.
Contents
Definition
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 ST cut is minimal.
Statement
The maxflow mincut theorem states
Linear program formulation
The maxflow problem and mincut problem can be formulated as two primaldual linear programs.
Maxflow (Primal)
Mincut (Dual)
maximize
minimize
subject to
subject to
The equality in the maxflow mincut 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 ▸
