graph_cost
def
For a finite vertex type V with [Fintype V], a pairwise distance function d : V → V → ℝ, and a simple graph T on V, graph_cost d T is defined as (1/2) * ∑ u : V, ∑ v : V, if T.Adj u v then d u v else 0.
Statement
noncomputable def graph_cost {V : Type*} [Fintype V] (d : V → V → ℝ) (T : SimpleGraph V) : ℝ
- Defined in
- arXiv:2610.23032 Section 4
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 1
- is_mstA simple graph T on a finite type V is a minimum spanning tree under d : V → V → ℝ if T is a tree (T.IsTree) and graph_cost d T ≤…
Read back from the Lean
Given a finite type V, a cost/weight function d : V → V → ℝ, and a simple graph T : SimpleGraph V, graph_cost d T is defined as half the sum over all ordered pairs of vertices (u, v) : V × V of d u v if u and v are adjacent in T, and 0 otherwise:
(1 / 2) * ∑ u : V, ∑ v : V, if T.Adj u v then d u v 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
/-- The total cost of a graph under distance function d. -/ noncomputable def graph_cost {V : Type*} [Fintype V] (d : V → V → ℝ) (T : SimpleGraph V) : ℝ := letI : DecidableRel T.Adj := Classical.decRel _ (1 / 2 : ℝ) * ∑ u : V, ∑ v : V, if T.Adj u v then d u v else 0