On Minimum Spanning Trees and Determinants

P. Wright

It is possible to find a minimum spanning tree in a weighted graph by using any of several well-known algorithms, but it is also possible to construct the entire set of all minimum spanning trees by a single unified process. This article shows that minimum spanning trees are built from certain building blocks, each of which is a special subset of the edges of the graphs. Linear algebra and discrete mathematics join forces to find them. Once the blocks have been identified, the trees themselves are easily assembled.