Definition:Minimum Spanning Tree
Jump to navigation
Jump to search
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.
Also known as
A minimum spanning tree is also known as an economy tree.
A minimum spanning tree can also be called the minimum connector for $G$.
Also see
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 4.1$: The Minimal Connector Problem: An Introduction to Trees