spanning_tree_congestion
def
The weighted spanning tree congestion of a graph H with edge weights w is the infimum, over all spanning trees T of H, of the maximum load of a fundamental cut of T.
Statement
noncomputable def spanning_tree_congestion {α : Type*} [Fintype α] [DecidableEq α] (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ) : ℕ
- Source
- step towards weighted_spanning_tree_congestion_hardness_gap
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 1
- fundamental_cut_loadThe load of the fundamental cut of an edge
ein a spanning treeTofH: the totalw-weight of the edges ofHwhose endpoints are…
- fundamental_cut_loadThe load of the fundamental cut of an edge
Lean source view module on GitHub
/-- Weighted spanning tree congestion `STC_w(H)`: the infimum of the maximum fundamental-cut load over all spanning trees of `H`, as a natural number. -/ noncomputable def spanning_tree_congestion {α : Type*} [Fintype α] [DecidableEq α] (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ) : ℕ := by classical exact sInf {c : ℕ | ∃ T : SimpleGraph α, T ≤ H ∧ T.IsTree ∧ T.edgeFinset.sup (fundamental_cut_load H w T) = c}