Max-flow min-cut theorem
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 total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.
The max-flow min-cut theorem is a special case of the duality theorem for linear programs 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 ∈ V being the source and the sink of N respectively.
Definition. The capacity of an edge is a mapping c : E → R+, denoted by cuv or c(u, v). It represents the maximum amount of flow that can pass through an edge.
Definition. A flow is a mapping f : E → R+, denoted by fuv or f (u, v), subject to the following two constraints:
Definition. The value of flow is defined by
where s is the source of N. It represents the amount of flow passing from the source to the sink.
Definition. An s-t cut C = (S, T) is a partition of V such that s ∈ S and t ∈ T. The cut-set of C is the set
...
Wikipedia