IsFeasibleMultiflow
A multicommodity flow function f : K → E → ℝ is feasible for capacities u : E → ℝ and demands d : K → ℝ on topology (G, H) if f is non-negative, total flow on each edge is at most capacity, and net outflow at each vertex equals source demand minus sink demand.
Statement
def IsFeasibleMultiflow {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V] (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) (u : E → ℝ) (d : K → ℝ) (f : K → E → ℝ) : Prop
- Defined in
- arXiv:2611.12330 Section 2
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Built on 1
- DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
- Used by 2
- HasFeasibleMultiflowAn instance (G, H, u, d) has a feasible multiflow if there exists some flow function f : K → E → ℝ satisfying IsFeasibleMultiflow G H u d f.
- HasIntegralMultiflowAn instance (G, H, u, d) has an integral multiflow if there exists a feasible multiflow f : K → E → ℝ such that every f i e is a natural…
Read back from the Lean
Given types V, E, and K with E and K finite and V having decidable equality, directed multigraphs G on vertices V and edges E and H on vertices V and demand edges K (each specified by src and tgt maps to V), an edge capacity function u : E → ℝ, a demand function d : K → ℝ, and a flow assignment f : K → E → ℝ, IsFeasibleMultiflow G H u d f is the proposition that:
1. (Nonnegativity) For every commodity i : K and edge e : E, f i e ≥ 0.
2. (Capacity constraint) For every edge e : E, the sum over all commodities i : K of f i e is at most u e.
3. (Flow conservation / demand satisfaction) For every commodity i : K and vertex v : V, the net outflow of commodity i at v—defined as (the sum over all e : E with G.src e = v of f i e) minus (the sum over all e : E with G.tgt e = v of f i e)—equals (if H.src i = v then d i else 0) - (if H.tgt i = v then d i else 0).
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
/-- Feasibility of a multiflow: nonnegativity, capacity bounds, and vertex conservation equations. -/ def IsFeasibleMultiflow {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V] (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) (u : E → ℝ) (d : K → ℝ) (f : K → E → ℝ) : Prop := (∀ i e, 0 ≤ f i e) ∧ (∀ e, (∑ i : K, f i e) ≤ u e) ∧ (∀ i v, (∑ e : E, if G.src e = v then f i e else 0) - (∑ e : E, if G.tgt e = v then f i e else 0) = (if H.src i = v then d i else 0) - (if H.tgt i = v then d i else 0))