Register

Number of minimum spanning trees

• edited by
2,175 views
7 votes
7 votes

The number of distinct minimum spanning trees for the weighted graph shown below is ___________.

 

• edited by
User Avatar

1 Answer

1 votes
1 votes
Answer should be 18

For left half all the 1's are compulsory to add to cover the vertices so we are left with 3 choices for the 2's

In the middle we have 2 choice we can take any one out of this 2's

In the right hand side all 1's are compulsory and we will left with 3 choices for 2's

3*2*3 =18
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
1
Nidhi Budhraja asked Aug 31, 2018
759 views
GATE Minimum Spanning Trees
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
User Avatar
1 votes
1 votes
1 answer
3
rahul sharma 5 asked Sep 16, 2017
740 views
[Discrete maths] Spanning trees
True/False; 1. Every tree is spanning tree.
True/False;1. Every tree is spanning tree.
User Avatar
1 votes
1 votes
3 answers
4
dd asked Mar 19, 2017
5,609 views
No of spanning Trees
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such a way that no two of these spanning trees have a common edge.
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such ...
User Avatar
Link Copied!