An undirected graph πΊ(π,πΈ) contains π(π>2) nodes named π£1,π£2,β¦,π£π.β¦
2017
An undirected graphΒ πΊ(π,πΈ)Β containsΒ π(π>2)Β nodes namedΒ π£1,π£2,β¦,π£π. Two nodesΒ π£πΒ andΒ π£πΒ are connected if and only ifΒ 0<β£πβπβ£β€2. Each edgeΒ (π£π,π£π)Β isΒ assigned a weightΒ π+π.
Β Β Β Β The cost of the minimum spanning tree of such a graph withΒ 10Β nodes is
- A.
88
- B.
91
- C.
49
- D.
21
Attempted by 109 students.
Show answer & explanation
Correct answer: B
Key idea: use Kruskal's algorithm: sort all edges by weight and repeatedly pick the smallest edge that does not form a cycle.
Edge weights in the graph:
Edges between consecutive nodes i and i+1 have weight 2i+1 (for i = 1..9): 3,5,7,9,11,13,15,17,19.
Edges between nodes two apart i and i+2 have weight 2i+2 (for i = 1..8): 4,6,8,10,12,14,16,18.
Apply Kruskal's algorithm (choose smallest edges without creating a cycle):
Pick edge (1,2) weight 3.
Pick edge (1,3) weight 4 (connects node 3 to the existing component).
Pick edge (2,4) weight 6.
Pick edge (3,5) weight 8.
Pick edge (4,6) weight 10.
Pick edge (5,7) weight 12.
Pick edge (6,8) weight 14.
Pick edge (7,9) weight 16.
Pick edge (8,10) weight 18 (this connects node 10 and completes the spanning tree).
Selected edge weights: 3, 4, 6, 8, 10, 12, 14, 16, 18.
Sum these weights: 3 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18 = 91.
Answer: The cost of the minimum spanning tree for the 10-node graph is 91.
A video solution is available for this question β log in and enroll to watch it.