493 views

1 Answer

Best answer
2 votes
2 votes

Depends on the method used to find number of MST's.

If you are using KIRCHOFF's THEOREM, then nothing special (except the theorem itself) is to be kept in mind.

If you are finding them manually using some counting tools (such as P and C etc), then :

1.Any spanning tree of a connected graph with n vertices will have exactly n-1 edges.

2. Look for the vertices which can be reached from multiple paths.Count the number of ways to reach that vertex.

3. Find a cycle(if any) whose edges are necessarily required to be traversed in order to make it an MST. Try to eliminate 1 edge at a time of that cycle and see how many ways are there to use edges of that cycle.

4.If it is a complete a graph that we have formula for number of MST's of a complete graph(google that).

All these points vary on individual basis.One may use them or not.I use these points.

selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
0 answers
3
Naveen Kumar 3 asked Nov 10, 2018
656 views
Let us assume that $G$($V$, $E$) is a weighted complete graph such that weight of the edge <$V_K$,$V_L$>=2|$K$-$L$|. The weight MST of $G$ with 100 vertices is __________...
0 votes
0 votes
3 answers
4
iarnav asked Apr 29, 2018
1,592 views
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST?Question2 ) Prim's algorithm works with negative weighted edges?