§1.1 — a flow in the Hitchcock network is maximum iff there is no augmenting path
ProvedEdmondsKarp.Scaling.isMaxFlow_iff_no_augPathConsider a problem on the network of Figure 1 with capacities , . A flow is a maximum flow if and only if there is no augmenting path relative to .
In the scaling method each phase stops when no augmenting path exists; this theorem says that it then holds a maximum flow of that phase's problem.
import Mathlib import Definitions.Def_EdmondsKarp_Scaling_Transport import Definitions.Def_EdmondsKarp_Scaling_Augmentation
namespace EdmondsKarp.Scaling
/-- §1.1, pp. 249–250, in the network of Figure 1: a flow is maximum if and only if there is no
augmenting path relative to it. -/
theorem isMaxFlow_iff_no_augPath {m n : ℕ} (T : Transport m n) (x : Flow m n) (hx : IsFlow T x) :
IsMaxFlow T x ↔ ¬ ∃ L : List (Node m n), IsAugPath T x L := by sorry
end EdmondsKarp.Scaling
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be natural numbers, an arbitrary real transport problem with no sign conditions, and an arc function.
Hypothesis. is a flow for , as defined above: nonnegativity, the capacity bounds and , and conservation at , at each , at each , and at .
Conclusion. The following are equivalent:
- is a maximum flow, i.e. for every flow for ;
- there is no list of nodes that is an augmenting path relative to in .
Here an augmenting path is a list of distinct nodes from to whose consecutive pairs all have positive residual capacity. Residual capacity is on , on , on , on , on , on , and for every other pair.
Degenerate cases.
- If or , the only flow is zero. It is maximum, no augmenting path exists, and both sides are true.
- If some or , no flow exists and the statement is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.