About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

Spanning trees

A spanning tree of a graph is a subgraph that contains (or "spans") every vertex of the original graph.

Because it is a tree, a spanning tree is connected and has no cycles. Because it is connected, the graph must be connected.
spanning tree The spanning tree of this graph is red.

A minimal spanning tree is often of interest when a weighted graph is used to model a problem. If the graph is weighted, the weight of a spanning tree is the sum of the weights of all of its edges. The minimal spanning tree is the spanning tree whose weight is the smallest of all possible spanning trees that you could draw for that graph.
minimal spanning tree The minimal spanning tree for this graph is red.

Copyright © 1999-2000 SciMathMN