Question 6276 – Data-Structures
December 4, 2023Averages
December 4, 2023GATE 2006
| Question 11 |
Consider a weighted complete graph G on the vertex set {v1, v2, …, vn} such that the weight of the edge (vi, vj) is 2|i – j|. The weight of a minimum spanning tree of G is:
| n-1 | |
| 2n-2 | |
 | |
| n2 |
Question 11 Explanation:
1) Including the initial call which means write the length of the spanning tree, a simple one it is. (Based on a particular graph)
2) Weight of the minimum spanning tree = 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) | = 2n – 2
2) Weight of the minimum spanning tree = 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) | = 2n – 2
Correct Answer: B
Question 11 Explanation:
1) Including the initial call which means write the length of the spanning tree, a simple one it is. (Based on a particular graph)
2) Weight of the minimum spanning tree = 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) | = 2n – 2
2) Weight of the minimum spanning tree = 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) | = 2n – 2