AFTD Auto-Formalizing Theoretical Domains

HasFeasibleMultiflow

def

An 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.

Statement

def HasFeasibleMultiflow {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…
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

Given types $V$, $E$, and $K$ with $E$ and $K$ finite and $V$ having decidable equality, a directed multigraph $G$ on vertex set $V$ with edge set $E$, a directed multigraph $H$ on vertex set $V$ with edge set $K$, an edge capacity function $u : E \to \mathbb{R}$, and a demand function $d : K \to \mathbb{R}$, HasFeasibleMultiflow G H u d asserts that there exists a flow function $f : K \to E \to \mathbb{R}$ such that $f$ is a feasible multiflow with respect to $(G, H, u, d)$ (that is, IsFeasibleMultiflow G H u d f).

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 multiflow for an instance (G, H, u, d). -/
def HasFeasibleMultiflow {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
See it in the graphDiscuss this resultChallenge it