IsMulticommodityFlow
Given a capacitated network on a finite vertex type V with decidable equality, and unicast sessions indexed by a finite type K with decidable equality, a directed flow function f : K → V → V → ℝ is a valid fractional multicommodity flow supporting common rate r if all flows are non-negative, for each pair u ≠ v the total bidirectional flow across the edge does not exceed the edge capacity, and flow conservation holds at every vertex with net outflow r at the source, net inflow r at the sink, and zero divergence elsewhere.
Statement
def IsMulticommodityFlow {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) (r : ℝ) (f : K → V → V → ℝ) : Prop
- Defined in
- arXiv:2610.10108, Sec. 2
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 2
- CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
- UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
- Used by 6
- flow_rate_mul_sep_le_cut_capacityIf a fractional multicommodity flow supports the common rate r, then for every vertex set S, r times the number of sessions crossing S is…
- flow_supports_rate_zeroOn any capacitated network net with unicast sessions sess, the common rate zero is always supported by fractional multicommodity flow.
- flow_supports_rate_scaled_capacitiesFractional multicommodity flow feasibility is homogeneous of degree one in (flow, rate, capacities): for T > 0, a flow of common rate T*r…
- flow_supports_rate_monoIf a fractional multicommodity flow on net with sessions sess supports common rate r, then for any non-negative rate r' ≤ r, rate r' is…
- flow_rate_mul_two_le_sum_cap_mul_distIf a fractional multicommodity flow on net supports the common rate r, and d is a symmetric, nonnegative, triangle-satisfying function on…
- FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…
Read back from the Lean
Given finite types with decidable equality $V$ and $K$, a capacitated network net on $V$, a collection of unicast sessions sess on $V$ indexed by $K$, a real number $r$, and a candidate flow function $f : K \to V \to V \to \mathbb{R}$, IsMulticommodityFlow net sess r f is the proposition that:
1. (Non-negativity) For all $k : K$ and all $u, v : V$, $0 \le f(k, u, v)$.
2. (Capacity constraint) For all $u, v : V$ such that $u \ne v$, the sum over all $k : K$ of $(f(k, u, v) + f(k, v, u))$ is at most the capacity net.cap s(u, v) of the undirected edge between $u$ and $v$.
3. (Flow conservation) For all $k : K$ and all $v : V$, the net outflow of commodity $k$ at vertex $v$, defined as $(\sum_{w : V} f(k, v, w)) - (\sum_{u : V} f(k, u, v))$, equals:
- $r$, if $v = \text{sess.src}(k)$;
- $-r$, if $v \ne \text{sess.src}(k)$ and $v = \text{sess.tgt}(k)$;
- $0$, otherwise.
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
/-- Predicate asserting that a directed flow tensor is a valid fractional multicommodity flow supporting common rate r. -/ def IsMulticommodityFlow {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) (r : ℝ) (f : K → V → V → ℝ) : Prop := (∀ k u v, 0 ≤ f k u v) ∧ (∀ u v, u ≠ v → (∑ k, (f k u v + f k v u)) ≤ net.cap s(u, v)) ∧ (∀ k v, (∑ w, f k v w) - (∑ u, f k u v) = if v = sess.src k then r else if v = sess.tgt k then -r else 0)