Proof of Theorem 1, p. 639 — the flow in an arc joining distinct strong components is at most
ProvedSendSplit.Existence.flow_le_sum_pos_demandgraph-theorynetwork-flowsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph, a demand vector and a flow for . For every arc of joining distinct strong components,
This bound is what makes the hypothesis of Theorem 1 enough to bound below by on such arcs.
Preamble
import Mathlib import Definitions.Def_SendSplit_Existence_Network import Definitions.Def_SendSplit_Existence_AugmentedGraph
Formal statement
namespace SendSplit.Existence
theorem flow_le_sum_pos_demand {n : ℕ} (G : ArcGraph n) (r : Fin n → ℝ)
(x : Fin n → Fin n → ℝ) (hx : IsFlow G r x) (p : Fin n × Fin n) (hp : p ∈ G.A)
(hpC : ¬ SameComponent G p.1 p.2) :
x p.1 p.2 ≤ ∑ i, max (r i) 0 := by sorry
end SendSplit.Existence
Source
Erickson, Monma, Veinott, Send-and-Split Method for Minimum-Concave-Cost Network Flows, Math. Oper. Res. 12 (1987), p. 639, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.