Gate2020 cs Q48

48Consider a graph G = (V, E), where V = {v₁, v₂, …, v₁₀₀}, E = {(v_i, v_j)|1≤i≤j≤100}, and weight of the edge (v_i, v_j) is |i – j|. The weight of the minimum spanning tree of G is _____.

Note – Numerical Type question

Option : A
Explanation :
If we consider a small graph with 5 vertices, then the minimum spanning tree will have a weight 4.
So, for n-vertices, MST weight would be (n – 1)
As n = 100 (no. of vertices), So, minimum spanning tree weight = (100 – 1) = 99

Forgot your password?

I agree with the Terms.