= Minimum spanning tree
{title2=$\min_T\sum_{e\in T}c_e$}
= MST
{c}
{synonym}
= Minimum-weight spanning tree
{synonym}
A <minimum spanning tree> of a finite connected undirected <weighted graph> minimizes the sum of <edge weights> over all <spanning trees>. <Kruskal's algorithm> repeatedly accepts a least-weight <edge> joining different current <connected components>. The cut-exchange argument preserves an optimum containing every accepted <edge>, including when weights tie.
For nonnegative <edge> costs, an <MST> gives a lower bound on a <travelling salesman tour>: removing one tour <edge> leaves a spanning path whose cost is no greater than the tour cost, and the <minimum spanning tree> costs no more than that path.
Nonnegativity is needed for this comparison. A triangle with all three <edge> weights equal to minus one has tour cost $-3$ and <minimum spanning tree> cost $-2$, so the latter is not a lower bound. The <MST> optimization problem itself permits negative <edge weights>.
Back to article page