Lemma 2 — using and later raises by at least 2
ProvedEdmondsKarp.ShortestPath.resDist_add_two_of_reversedConsider a run of the labeling method with fewest-arc augmenting paths , and let be the distance from to in the residual network of . If , and , then
Since never exceeds while finite, this lemma limits how often a pair of nodes can alternate in augmenting paths.
Formalization Note The inequality is in ℕ∞, with .
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
namespace EdmondsKarp.ShortestPath
/-- Lemma 2 (p. 251): if `k < l`, `(u, v) ∈ P^k` and `(v, u) ∈ P^l`, then
`δ^l(s, t) ≥ δ^k(s, t) + 2`. -/
theorem resDist_add_two_of_reversed {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
(K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P)
(k l : ℕ) (hkl : k < l) (hl : l < K) (u v : V)
(huv : (u, v) ∈ pathArcs (P k)) (hvu : (v, u) ∈ pathArcs (P l)) :
resDist N (f k) N.s N.t + 2 ≤ resDist N (f l) N.s N.t := by sorry
end EdmondsKarp.ShortestPath
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. is a network on a finite node type :
- a source and a sink with ;
- a finite loop-free set of ordered pairs with ;
- real capacities on .
Residual arcs. means that either and , or and .
Paths and distance. A directed path from to in is a list of pairwise distinct nodes from to whose consecutive pairs (steps) lie in . is the minimum number of steps of such a path, or if there is none.
Augmenting paths. An augmenting path is a directed path from to . A shortest one has the minimum number of steps among all augmenting paths.
Augmentation. is defined as follows:
-
it adds at , where is the minimum over the steps of:
- if both ;
- if only ;
- otherwise.
It is if there are no steps.
-
on it adds and subtracts :
- is nonzero only if is a step. It then equals if , and otherwise.
- is nonzero only if is a step. It then equals if , and otherwise.
-
it leaves all other values unchanged.
Run. The hypothesis is a run of length :
- is a flow ( on , on , conservation at every node);
- for each , is a shortest augmenting path relative to , and .
Theorem. For every such run, all indices and all nodes : if is a step of and is a step of , then
Degenerate cases. The statement is vacuous unless .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.