Proposition 2 — new residual arcs are reversals of arcs of
ProvedEdmondsKarp.ShortestPath.residual_next_subConsider a run of the labeling method with fewest-arc augmenting paths , and write for the residual network of . For every and all nodes :
where means that is one of the consecutive pairs of the node sequence .
The only arcs an augmentation can add to the residual network are the reversals of arcs of the augmenting path; this is used in Lemma 1 and Proposition 3.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation import Definitions.Def_EdmondsKarp_ShortestPath_Run
namespace EdmondsKarp.ShortestPath
/-- Proposition 2 (p. 252): if `(u, v) ∈ N^{k+1}` then `(u, v) ∈ N^k` or `(v, u) ∈ P^k`. -/
theorem residual_next_sub {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 : V) (h : ResArc N (f (k + 1)) u v) :
ResArc N (f k) u v ∨ (v, u) ∈ pathArcs (P k) := 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 .
Steps and augmenting paths. The steps of a list are its consecutive pairs. An augmenting path relative to is a list of pairwise distinct nodes from to whose steps all lie in . 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 of:
- if both ;
- if only ;
- if .
It is if there are no steps.
-
on it adds and subtracts , where:
- is unless is a step of . It then equals if , and otherwise.
- is unless is a step of . 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 over the pairs in );
- for each , is a shortest augmenting path relative to , and .
Theorem. For every such run, every and all nodes :
Degenerate cases. For the statement is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.