Mathematical Abstraction

A spanning tree is a tree (i.e., a set of edges with no undirected cycles). How find one?

The cost of a spanning tree is the sum of the weights of the edges included in that spanning tree.

A minimum spanning tree is a spanning tree with the smallest possible cost.


next up previous
Next: Simple Verification Up: MINIMUM SPANNING TREES Previous: Water For Everyone