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

Question

I do not want to find all the minimum spanning trees, but I want to know how many of them are, here is my method:

• Find one minimum spanning tree using the prim or kruskal algorithm, and then find the weights of all spanning trees and increase the work counter when it is equal to the weight of the minimum spanning tree.

I could not find any method for finding the weights of all spanning trees, and the number of spanning trees could be very large, so this method may not be acceptable for the problem. Since the number of minimal spanning trees is exponential, counting them would not be a good idea.

• All weights will be positive.
• We can also assume that the weight will not be displayed more than three times on 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 minimal spanning tree in the graph, where the weights of the vertices are different. I think the best way to find the minimum spanning tree number should be something using this property.

EDIT :

I found a solution to this problem, but I'm not sure why this works. Can someone explain this.

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

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

Together, these two facts imply that our answer will be the result of a number of ways, using the Kruskal algorithm, to insert edges of length K (for each possible value of K). Since there are no more than three edges of any length, different cases can be rough, and related components can be determined after each step, as would be usual.

Answer 1

Looking at the Prim algorithm, he says he re-adds the edge with the lowest weight. What happens if there is more than one edge with the lowest weight that can be added? Perhaps choosing one can give a different tree than when choosing another.

If you use a primitive algorithm and run it for each edge as the source edge, and also perform all the communications that you encounter. Then you will have a Forest containing all the minimum spanning trees that the Prim algorithm can find. I do not know if this corresponds to a forest containing all possible minimal spanning trees.

It still comes to finding all the minimum spanning trees, but I don’t see a simple way to determine whether another choice will give the same tree or not.

Answer 2

MST and their score on the chart are well understood. See for example: http://www14.informatik.tu-muenchen.de/konferenzen/Jass08/courses/1/pieper/Pieper_Paper.pdf .