AFTD Auto-Formalizing Theoretical Domains

HasIntegralMultiflow

def

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
See it in the graphDiscuss this resultChallenge it