1 1 vote https://gateoverflow.in/?qa=blob&qa_blobid=15165260876214054240 Graph Theory minimum-spanning-tree + – Ravi_1511 508 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
2 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 Habibkhan answered Nov 2, 2016 Habibkhan comment Share Follow 0 reply Please log in or register to add a comment.
