Max-flow min-cut theorem

related topics
{math, number, function}
{line, north, south}
{math, energy, light}
{system, computer, user}
{ship, engine, design}

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.

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 S-T cut is minimal.

Statement

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.

Max-flow (Primal)

Min-cut (Dual)

maximize |f| = \sum_{j: (s, j) \in E} f_{sj}

minimize \sum_{(i, j) \in E} c_{ij} d_{ij}

subject to


\begin{array}{rclr} f_{ij} & \leq & c_{ij} & (i, j) \in E \\
\sum_{j: (i, j) \in E} f_{ij} - \sum_{j: (j, i) \in E} f_{ji} & \geq & 0 & i \in V, i \neq t \\
f_{ij} & \geq & 0 & (i, j) \in E\\
\end{array}

subject to

\begin{array}{rclr}
d_{ij} - p_i + p_j & \geq & 0 & (i, j) \in E \\
p_s & = & 1 & \\
p_t & = & 0 & \\
p_i & \geq & 0 & i \in V \\
d_{ij} & \geq & 0 & (i, j) \in E
\end{array}

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 ▸

related documents
Antiderivative
Power set
Julia set
Heapsort
Blackboard bold
Polytope
Liouville number
Gamma function
Hypercomplex number
Separation axiom
Boolean algebra (structure)
Finite difference
Tychonoff space
Positive-definite matrix
Stone–Weierstrass theorem
Cardinality
Weak topology
Yoneda lemma
Morphism
Cauchy's integral formula
Quine (computing)
Inverse limit
Banach fixed point theorem
Even and odd permutations
Supervised learning
Linear equation
Solvable group
Topological group
Probability space
Separable space