DT Q30
Linked Data Question 30 and 31
An undirected graph G(V, E) contains n(n > 2) nodes named v1 , v2 , …, vn . Two nodes vi , vj are connected if and only if 0 < | i – j | ≤ 2. Each edge (vi , vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.
0. What will be the cost of the Minimum Spanning Tree (MST) of such a graph with n nodes?
- Option : B
- Explanation : If we construct graph for n = 6 vertices
(V1
, V2
, V3
, V4
, V5
, V6
)
then minimum spanning tree for this graph is
total weight = 31
so if we put n = 6 in option “b” then we get 31
i.e. x2 – n + 1
(6)2 – 6 + 1 ⇒ 36 – 6 + 1 ⇒ 31.
