§1.1 — a flow is maximum iff it admits no augmenting path
ProvedEdmondsKarp.ShortestPath.isMaxFlow_iff_no_augPathLet be a network with source , sink and return arc , and let be a flow in . Then
The direction "" holds because augmenting along a path increases ; the direction "" is the statement that a flow is not maximum only if there is an augmenting path. It justifies the stopping rule of the labeling method: the method stops exactly at a maximum flow.
import Mathlib import Definitions.Def_EdmondsKarp_ShortestPath_Network import Definitions.Def_EdmondsKarp_ShortestPath_Augmentation
namespace EdmondsKarp.ShortestPath
/-- §1.1, pp. 249–250: a flow `f` in `N` is a maximum flow if and only if there is no augmenting path
relative to `f`. -/
theorem isMaxFlow_iff_no_augPath {V : Type} [Fintype V] [DecidableEq V] (N : Network V)
(f : V → V → ℝ) (hf : IsFlow N f) :
IsMaxFlow N f ↔ ¬ ∃ P : List V, IsAugPath 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 network on a finite node type :
- a source and a sink with ;
- a finite set of ordered pairs, with no loops and ;
- real capacities with on (arbitrary off ).
Flow. A function is a flow if it satisfies:
- on ;
- on (the return arc is uncapacitated);
- at every node , the sum of over the pairs of leaving equals the sum over those entering .
Maximum flow. is a maximum flow if it is a flow and for every flow .
Augmenting path. An augmenting path relative to is a list of pairwise distinct nodes, starting at and ending at , each of whose consecutive pairs satisfies either and , or and .
Theorem. For every network and every flow in :
The capacities are arbitrary positive reals; they are not assumed to be integers or rationals.
Degenerate cases.
- has at least two elements.
- If , no augmenting path exists. Every flow then has by conservation at , so the statement says every flow is a maximum flow.
- The hypothesis that is a flow can always be satisfied, since the zero function is a flow.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.