SatisfiesC4
Real-valued capacities u : E → ℝ and demands d : K → ℝ satisfy condition (C4) on topology (G, H) if for every binary edge-length function ℓ : E → ENNReal with ℓ e = 0 ∨ ℓ e = 1 for all e, the demand-weighted shortest path sum ∑ i, ENNReal.ofReal (d i) * directedDistENN G ℓ (H.src i) (H.tgt i) is at most the capacity-weighted sum ∑ e, ENNReal.ofReal (u e) * ℓ e.
Statement
noncomputable def SatisfiesC4 {V E K : Type*} [Fintype E] [Fintype K] (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) (u : E → ℝ) (d : K → ℝ) : Prop
- Defined in
- arXiv:2611.12330 Section 3, Condition (C4)
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Built on 2
- DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
- directedDistENNThe shortest path distance directedDistENN G ℓ u v from vertex u to vertex v in a directed multigraph G with edge lengths ℓ : E → ENNReal,…
- Used by 1
- BelongsToS4A directed multiflow topology (G, H) belongs to S_4 if for every non-negative capacities u : E → ℝ and demands d : K → ℝ, satisfying…
Read back from the Lean
For finite types E and K, an arbitrary type V, directed multigraphs G on (V, E) and H on (V, K), and real-valued functions u : E → ℝ and d : K → ℝ, SatisfiesC4 G H u d asserts that:
For every length function ℓ : E → ENNReal such that for all e : E, ℓ e = 0 or ℓ e = 1,
the sum over i : K of ENNReal.ofReal (d i) * directedDistENN G ℓ (H.src i) (H.tgt i) is less than or equal to the sum over e : E of ENNReal.ofReal (u e) * ℓ e.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Binary edge-length condition (C4) for directed multiflows. -/ noncomputable def SatisfiesC4 {V E K : Type*} [Fintype E] [Fintype K] (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) (u : E → ℝ) (d : K → ℝ) : Prop := ∀ ℓ : E → ENNReal, (∀ e, ℓ e = 0 ∨ ℓ e = 1) → (∑ i : K, ENNReal.ofReal (d i) * directedDistENN G ℓ (H.src i) (H.tgt i)) ≤ (∑ e : E, ENNReal.ofReal (u e) * ℓ e)