2
$\begingroup$

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

enter image description here

When running Kruskal's you can end up with:

enter image description here

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?

$\endgroup$
  • 2
    $\begingroup$ What research have you done? What approaches have you considered, and why did you reject them? A google search immediately turns up several reasonable-looking resources, e.g., www14.informatik.tu-muenchen.de/konferenzen/Jass08/courses/1/…. We want you to do a significant amount of research before asking. $\endgroup$ – D.W. Mar 9 '16 at 4:42
  • $\begingroup$ @D.W. Yep, I noticed that, that's why I removed my comment immediately ;) $\endgroup$ – orezvani Mar 9 '16 at 5:12
  • $\begingroup$ As a side question, could anyone provide references or examples of practical applications of this problem? $\endgroup$ – Carlos Linares López Mar 9 '16 at 12:25
2
$\begingroup$

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.

  1. It establishes that Kruskal's algorithm can find every MST.
  2. 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.
  3. It proves that the number of MSTs is the product of the number of spanning forests in the multigraph for each block-defining weight.
  4. Finally, the number of spanning forests for a multigraph can be computed by Kirchhoff's theorem.
$\endgroup$
1
$\begingroup$

It needs to be noted that there could be an exponential number of MSTs in a graph. For example, consider a complete undirected graph, where the weight of every edge is 1. The number of minimum spanning trees in such graph is exponential (equal to the number of spanning trees of the network).

The following paper proposes an algorithm for enumerating and generating all minimum spanning trees of the network:

Yamada, Takeo, Seiji Kataoka, and Kohtaro Watanabe. "Listing all the minimum spanning trees in an undirected graph." International Journal of Computer Mathematics 87.14 (2010): 3175-3185.

Be careful, there are plenty of codes for enumerating spanning trees, but not minimum spanning trees. However, the algorithm to do so is very similar.

$\endgroup$
  • 3
    $\begingroup$ An exponential number of MST's is not a barrier to a polynomial-time algorithm to count the number of MST's. The question asks about counting the number of MST's, which is different from enumerating all MST's. $\endgroup$ – D.W. Mar 9 '16 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.