HasIntegralMultiflow
An 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 number.
Statement
def HasIntegralMultiflow {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V] (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) (u : E → ℝ) (d : K → ℝ) : Prop
- Defined in
- arXiv:2611.12330 Section 2
- 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.
- IsFeasibleMultiflowA multicommodity flow function f : K → E → ℝ is feasible for capacities u : E → ℝ and demands d : K → ℝ on topology (G, H) if f is…
Read back from the Lean
Given types V, E, and K, with E and K finite and V having decidable equality, a directed multigraph G with vertices V and edges E, a directed multigraph H with vertices V and edges/commodities K, edge capacity function u : E → ℝ, and demand function d : K → ℝ, HasIntegralMultiflow G H u d asserts that:
There exists a flow function f : K → E → ℝ such that:
1. f is a feasible multiflow (IsFeasibleMultiflow G H u d f), meaning:
- For all i : K and e : E, 0 ≤ f i e;
- For all e : E, $\sum_{i \in K} f(i, e) \le u(e)$;
- For all i : K and v : V, the net outflow of commodity i at v (i.e., the sum of $f(i, e)$ over edges e with source v, minus the sum of $f(i, e)$ over edges e with target v) equals $(d(i) \text{ if } H.\text{src}(i) = v \text{ else } 0) - (d(i) \text{ if } H.\text{tgt}(i) = v \text{ else } 0)$;
2. For all i : K and e : E, there exists a natural number n : ℕ such that f i e = n (i.e., all flow values are non-negative integers).
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
/-- Existence of a feasible integral multiflow for an instance (G, H, u, d). -/ def HasIntegralMultiflow {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V] (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) (u : E → ℝ) (d : K → ℝ) : Prop := ∃ f : K → E → ℝ, IsFeasibleMultiflow G H u d f ∧ ∀ i e, ∃ n : ℕ, f i e = n