Definition:Minimum Spanning Tree

From ProofWiki
Jump to: navigation, 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.


For a given $G$, the minimum spanning tree may not be unique.


It can also be called the minimum connector for $G$.


Also known as

A minimum spanning tree is also known as an economy tree.


Sources