![GATE 2014 [Set-2]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
GATE CS 2025 FN
April 3, 2025GATE 2014 [Set-2]
April 3, 2025GATE 2014 [Set-2]
|
Question 62
|
The number of distinct minimum spanning trees for the weighted graph below is _______.
|
6
|
|
|
7
|
|
|
8
|
|
|
9
|
Question 62 Explanation:
Minimum Spanning Tree:
From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.
So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.
Correct Answer: A
Question 62 Explanation:
Minimum Spanning Tree:
From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.
So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.