HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Counting Minimum Spanning Trees

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
minimumspanningcountingtrees

Problem

I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph $G=(V,E)$ given by

When running Kruskal's you can end up with:

However, as you might note, there are several other minimum spanning trees that are still valid. An example would be getting rid of edge $BD$ and adding edge $AB$ or $CB$. So how can you determine the total number of different minimum spanning trees that exist in the graph, without having to inspect for all the different possibilities?

Solution

The best exposition on how to count the number of minimum spanning trees is, as far as I have seen, a stackoverflow answer by j_random_hacker.

In the course to answer a different question, that answer explains very well an algorithm that counts the number of MSTs.

  • It establishes that Kruskal's algorithm can find every MST.



  • It breaks up the Kruskal's algorithm into a series of blocks, each of which consists of a sequence of adding the edges of the same weight into a component multigraph that has been built in the previous block of operation.



  • It proves that the number of MSTs is the product of the number of spanning forests in the multigraph for each block-defining weight.



  • Finally, the number of spanning forests for a multigraph can be computed by Kirchhoff's theorem.

Context

StackExchange Computer Science Q#54178, answer score: 3

Revisions (0)

No revisions yet.