260 views

1 Answer

2 votes
2 votes

In the given graph , we have 6 vertices .We know the conditions for MST :

a) In an MST , if we have n vertices ,we should cover all n vertices and we have n-1 edges

b) Also the sum of cost should be minimal

c) No cycle formation should occur in the MST

d) The MST should be connected.

So applying Kruskals algo , we choose the 3 edges having  edge weights 1 so we need 2 more edges to be included in the MST.Now we have 3 edges available of edge weights 2 .But we can choose only those 2 edges containing edge weight 2 which are incident on vertex labelled u in the graph and we can not choose that edge which is incident on vertex labelled v as this will make the MST disconnected.

In short we have only 1 way to select minimum 5 edges to form the MST as mentioned above.

So no of MSTs possible  = 1

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
2 answers
3
Prince Sindhiya asked Dec 21, 2018
565 views
I got 41 as answer please verify
3 votes
3 votes
3 answers
4
kapilbk1996 asked Feb 2, 2018
4,178 views
How to approach such questions ? Please provide detailed solution. Answer given is option C