How to find total number of minimum spanning trees in a graph?

Question

I don't want to find all the minimum spanning trees but I want to know how many of them are there, here is the method I considered:

• Find one minimum spanning tree using prim's or kruskal's algorithm and then find the weights of all the spanning trees and increment the running counter when it is equal to the weight of minimum spanning tree.

I couldn't find any method to find the weights of all the spanning trees and also the number of spanning trees might be very large, so this method might not be suitable for the problem. As the number of minimum spanning trees is exponential, counting them up wont be a good idea.

• All the weights will be positive.
• We may also assume that no weight will appear more than three times in the graph.
• The number of vertices will be less than or equal to 40,000.
• The number of edges will be less than or equal to 100,000.

There is only one minimum spanning tree in the graph where the weights of vertices are different. I think the best way of finding the number of minimum spanning tree must be something using this property.

EDIT:

I found a solution to this problem, but I am not sure, why it works. Can anyone please explain it.

Solution: The problem of finding the length of a minimal spanning tree is fairly well-known; two simplest algorithms for finding a minimum spanning tree are Prim's algorithm and Kruskal's algorithm. Of these two, Kruskal's algorithm processes edges in increasing order of their weights. There is an important key point of Kruskal's algorithm to consider, though: when considering a list of edges sorted by weight, edges can be greedily added into the spanning tree (as long as they do not connect two vertices that are already connected in some way).

Now consider a partially-formed spanning tree using Kruskal's algorithm. We have inserted some number of edges with lengths less than N, and now have to choose several edges of length N. The algorithm states that we must insert these edges, if possible, before any edges with length greater than N. However, we can insert these edges in any order that we want. Also note that, no matter which edges we insert, it does not change the connectivity of the graph at all. (Let us consider two possible graphs, one with an edge from vertex A to vertex B and one without. The second graph must have A and B as part of the same connected component; otherwise the edge from A to B would have been inserted at one point.)

These two facts together imply that our answer will be the product of the number of ways, using Kruskal's algorithm, to insert the edges of length K (for each possible value of K). Since there are at most three edges of any length, the different cases can be brute-forced, and the connected components can be determined after each step as they would be normally.

Dardanelles

Answer 1

Looking at Prim's algorithm, it says to repeatedly add the edge with the lowest weight. What happens if there is more than one edge with the lowest weight that can be added? Possibly choosing one may yield a different tree than when choosing another.

If you use prim's algorithm, and run it for every edge as a starting edge, and also exercise all ties you encounter. Then you'll have a Forest containing all minimum spanning trees Prim's algorithm is able to find. I don't know if that equals the forest containing all possible minimum spanning trees.

This does still come down to finding all minimum spanning trees, but I can see no simple way to determine whether a different choice would yield the same tree or not.

Aubine

the problem which i am trying to solve has edges upto 100,000. So it will take a long time to run prim's algorithm from each edge. – Dardanelles

You could speed it up by checking whether any intermediate graph is a graph you have encountered as intermediate graph already. Any such graph is certain to yield minimum spanning trees we already have. Although this will cost you in memory. At any rate it will remain slow. – Aubine

You could run the algorithm for each starting edge simultaneously : start by making a forest of all trees that are the result of the first step in Prim's algorithm. (from 40k vertices this yields abt. 20k trees) Then do the next step of the algorithm on each of the trees in that forest, and create a new forest containing the trees with two edges (likely removing even more duplicates). Every step will keep eliminating duplicates, and this structure also easily allows to handle multiple possibilities as the next step by adding all possibilities to the next generation forest – Aubine

You can find out if to different same- weighted edges form the same spanning tree, by finding out if they are a part of the same circle. this can be find out by DFS, in two ways, the simpler one from them is by running DFS, and then up siding the direction of the edges of the tree that you got, and then running it again – Smallish

Answer 2

MST and their count in a graph are well-studied. See for instance: http://www14.informatik.tu-muenchen.de/konferenzen/Jass08/courses/1/pieper/Pieper_Paper.pdf.

Conjugal