§1.1 — augmentation along an augmenting path yields a flow of value
ProvedEdmondsKarp.ShortestPath.augment_isFlowLet be a network with source , sink and return arc , let be a flow in , and let be an augmenting path relative to , with as defined by Cases (a)–(c). Let be the function obtained from by the augmentation along . Then
This is the step that makes the labeling method well defined: every augmentation produces a flow of strictly larger value.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation
namespace EdmondsKarp.ShortestPath
/-- §1.1, p. 249: for an augmenting path `P` relative to a flow `f`, `ε = min ε_i > 0`, and the
augmented `f′` is a flow in `N` with `f′(t, s) = f(t, s) + ε`. -/
theorem augment_isFlow {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
(f : V → V → ℝ) (P : List V) (hf : IsFlow N f) (hP : IsAugPath N f P) :
0 < pathEps N f P ∧ IsFlow N (augment N f P) ∧
augment N f P N.t N.s = f N.t N.s + pathEps N f P := by sorry
end EdmondsKarp.ShortestPath
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. is a finite node type with decidable equality, and is a network on it:
- a source and a sink with ;
- a finite set of ordered pairs, with no loops and ;
- a real capacity with on .
Flow. is a flow if it satisfies:
- on ;
- on ;
- at every node (including and ), the sum of over equals the sum of over .
Residual arcs. is in if either and , or and .
Augmenting path. An augmenting path is a list of pairwise distinct nodes with and , each of whose steps lies in .
The number . is the minimum over the steps of of:
- if both ;
- if only ;
- if .
It is if there are no steps.
Augmented function. The augmented function is defined as follows:
- .
- For , , where:
- is unless is a step of . If it is a step, is when , and otherwise.
- is unless is a step of . If it is a step, is when , and otherwise.
- at every other pair.
Theorem. For every such , every and every list : if is a flow in and is an augmenting path relative to , then
Degenerate cases.
- has at least two elements because .
- An augmenting path has at least one step, so is not the default value .
- If no augmenting path exists (for example when ), the statement is vacuous for that .
- The third conjunct holds directly by the definition of .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.