fundamental_cut_load
def
The load of the fundamental cut of an edge e in a spanning tree T of H: the total w-weight of the edges of H whose endpoints are separated by deleting e from T.
Statement
noncomputable def fundamental_cut_load {α : Type*} [Fintype α] [DecidableEq α] (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ) (T : SimpleGraph α) (e : Sym2 α) : ℕ
- Source
- step towards weighted_spanning_tree_congestion_hardness_gap
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 1
- spanning_tree_congestionThe weighted spanning tree congestion of a graph
Hwith edge weightswis the infimum, over all spanning treesTofH, of the…
- spanning_tree_congestionThe weighted spanning tree congestion of a graph
Lean source view module on GitHub
/-- Weighted load of the fundamental cut of `e` in `T`: the sum of the weights of the `H`-edges crossing the cut induced by deleting `e` from `T`. -/ noncomputable def fundamental_cut_load {α : Type*} [Fintype α] [DecidableEq α] (H : SimpleGraph α) [DecidableRel H.Adj] (w : Sym2 α → ℕ) (T : SimpleGraph α) (e : Sym2 α) : ℕ := by classical exact ∑ uv ∈ H.edgeFinset, if Sym2.lift ⟨fun u v => ¬ (T.deleteEdges {e}).Reachable u v, fun _ _ => propext ⟨fun h hr => h hr.symm, fun h hr => h hr.symm⟩⟩ uv then w uv else 0