Proposition 3 — residual distances from and to never decrease
ProvedEdmondsKarp.ShortestPath.resDist_monotoneConsider a run of the labeling method in a network with source and sink , in which each augmentation is along an augmenting path having fewest arcs. Let be the distance from to in the residual network of . For every and every node ,
and
This monotonicity of distances under shortest-path augmentation is the key ingredient of Lemma 2.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
namespace EdmondsKarp.ShortestPath
/-- Proposition 3 (p. 252): for `k = 0, 1, 2, …` and all `u`, `δ^k(s, u) ≤ δ^{k+1}(s, u)` (1) and
`δ^k(u, t) ≤ δ^{k+1}(u, t)` (2). -/
theorem resDist_monotone {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
(K : ℕ) (f : ℕ → V → V → ℝ) (P : ℕ → List V) (hrun : IsShortestRun N K f P)
(k : ℕ) (hk : k < K) (u : V) :
resDist N (f k) N.s u ≤ resDist N (f (k + 1)) N.s u ∧
resDist N (f k) u N.t ≤ resDist N (f (k + 1)) u 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 starting at and ending at , all of whose consecutive pairs (steps) lie in . The residual distance is
with if there is no such path and .
Augmenting paths. An augmenting path is a directed path from to . A shortest augmenting path has no more steps than any other augmenting path.
Augmentation. is defined as follows:
-
it adds at , where is the minimum over the steps of:
- if both ;
- if only ;
- if .
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, every and every node :
with the comparison taken in .
Degenerate cases.
- For the statement is vacuous.
- For the first inequality is , and for the second is .
- If is unreachable after the step, the right-hand side is and the inequality holds trivially.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.