Theorem 15.1 — Max-Flow Min-Cut
ProvedVanderbeiLP.Networks.max_flow_min_cutLet be a network with source , sink and finite upper bounds on the arcs. Then the maximum value of over feasible flows equals the minimum value of over cuts : there is a real number such that
both the maximum and the minimum being attained.
The theorem is the network instance of LP duality and underlies the analysis of maximum-flow algorithms.
Formalization Note "Maximum" and "minimum" are stated with attainment (IsGreatest, IsLeast). The hypotheses and are implicit in the book: the extra arc must not be a loop, and the upper-bounded problem is feasible only if . Connectedness is not assumed (the Chapter 14 assumption is not restated in Chapter 15, and the theorem does not need it).
import Mathlib import Definitions.Def_VanderbeiLP_Networks_MaxFlow
namespace VanderbeiLP.Networks
/-- **Theorem 15.1, Max-Flow Min-Cut** (Vanderbei, *Linear Programming*, 4th ed., p. 234). In the
maximum-flow problem on a network `(N, A)` with source `s ≠ t` sink and finite nonnegative upper
bounds `u_{ij}`, the maximum value of `x_{ts}` over feasible flows equals the minimum value of
`κ(C)` over cuts `C`; both extrema are attained. -/
theorem max_flow_min_cut {N : Type*} [Fintype N] [DecidableEq N]
(A : Finset (N × N)) (hA : IsNetwork A) (u : N × N → ℝ) (hu : ∀ a ∈ A, 0 ≤ u a)
(s t : N) (hst : s ≠ t) :
∃ v : ℝ,
IsGreatest {w : ℝ | ∃ x : N × N → ℝ, IsMaxFlowFeasible A u s t x w} v ∧
IsLeast {κ : ℝ | ∃ C : Finset N, IsCut s t C ∧ cutCapacity A u C = κ} v := by sorry
end VanderbeiLP.Networks
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.