DT Q23

Home
DT Q23

23Consider a weighted complete graph G on the vertex set {v₁, v₂,..., v_n} such that the weight of the edge (v_i, v_j) is 2 |i - j|. The weight of a minimum spanning tree of G is

Option : B
Explanation :
Minimum spanning tree of such a graph is

Weight of the minimum spanning tree
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2

Forgot your password?

I agree with the Terms.