Theorem 1, 5° ⇒ 6° — nonnegative circuit slopes give minimum-cost chains to in the augmented graph
ProvedSendSplit.Existence.five_implies_sixLet be a graph with arc cost functions , and write for the limiting right-derivative (slopeAtInfty). Suppose condition 5° of Theorem 1 holds:
Let contain exactly one node of each sink strong component of and no other node, and form the augmented graph by appending a node and arcs , . Give the arc costs : for arcs inside a strong component of , an arbitrary real for arcs of joining distinct strong components, and an arbitrary real for the appended arcs . Then from every node of (including itself) there is a minimum-cost chain to : a chain (directed walk) of real cost whose cost is at most that of every chain from to .
This is the implication 5° ⇒ 6° of Theorem 1: the circuit condition 5°, which does not involve demands, yields the shortest-chain test 6° and the potentials used for 7°.
Formalization Note. Chains are walks (lists of nodes of , none standing for ) and may repeat nodes; costs live in (EReal); "minimum-cost" means attained, with real cost.
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_AugmentedGraph
namespace SendSplit.Existence
theorem five_implies_six {n : ℕ} (G : ArcGraph n) (c : Fin n → Fin n → ℝ → ℝ)
(h5 : ∀ C, IsSimpleCircuit G C → 0 ≤ ∑ p ∈ C, slopeAtInfty (c p.1 p.2))
(S : Finset (Fin n)) (hS : IsSinkSelection G S) (b : Fin n → Fin n → ℝ) (bν : Fin n → ℝ)
(u : Option (Fin n)) :
HasMinCostChain G S (augCost G c b bν) u := by sorry
end SendSplit.Existence