Counting and Constructing Minimal Spanning Trees

P. Wright

We revisit the minimal spanning tree problem in order to develop a theory of construction and counting of the minimal spanning trees in a network. The theory indicates that the construction of such trees consists of many different choices, all independent of each other. These results suggest a block approach to the construction of all minimal spanning trees in the network, and an algorithm to that effect is outlined as well as a formula for the number of minimal spanning trees.

Hardcopy (with pictures) available upon request.