Max-flow min-cut theorem

In a capacitated network, the greatest feasible flow from a source to a sink equals the smallest capacity of any cut separating them.

Maximum flow problem: The problem of finding the greatest feasible flow from a designated source to a sink in a capacitated network. The theorem gives an exact certificate for the optimum of this network optimization problem.
Ford–Fulkerson algorithm: A method for finding maximum flow by repeatedly augmenting along residual source-to-sink paths. Its stopping condition exposes a cut whose capacity certifies the computed flow is maximum.
Lester R. Ford Jr.: An American mathematician who coauthored foundational work on network flows and the Ford–Fulkerson method. Ford coauthored the 1956 paper that established the theorem in its algorithmic setting.
Weak duality: A principle stating that every feasible solution to a primal problem and its dual gives an inequality between their objective values. Weak duality gives the flow-below-cut bound; the theorem proves equality is attained.
Flow conservation: A constraint requiring total incoming flow to equal total outgoing flow at every vertex except the source and sink. Conservation makes the net flow across every source–sink cut equal the flow's value.
Edmonds–Karp algorithm: A Ford–Fulkerson implementation that chooses shortest augmenting paths by breadth-first search. It uses the theorem's maximum-flow certificate and runs in polynomial time.
Delbert R. Fulkerson: An American mathematician whose work helped establish network flow as a field of optimization. Fulkerson coauthored the foundational treatment linking maximum flows and minimum cuts.
Min-cost flow: A network optimization problem that sends a required amount of flow at minimum total edge cost. It optimizes cost rather than flow value, so cut capacity alone does not specify its solution.
Cut (graph theory): A partition of a graph's vertices into two sets, with a cut consisting of edges crossing between them. A source–sink cut bounds every feasible flow by the capacity of its forward-crossing edges.
Bipartite matching: A set of edges in a bipartite graph with no shared endpoints. A flow network reduces maximum matching to maximum flow, while cuts certify matching-size bounds.

Linked from 6 pages