Definition:Minimum Spanning Tree
From ProofWiki
Definition
Let $G$ be a weighted graph.
The minimum spanning tree for $G$ is a spanning tree for $G$ which has a minimum total weight.
For a given $G$, the minimum spanning tree may not be unique.
It can also be called the minimum connector for $G$.
It is also known as an economy tree.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 4.1$
