Find the minimum spanning distance and the corresponding number of edges for…
2023
Find the minimum spanning distance and the corresponding number of edges for the following graph
- A.
10, 3
- B.
11 ,4
- C.
15, 4
- D.
28, 7
Attempted by 173 students.
Show answer & explanation
Correct answer: B
To find the minimum spanning distance, we use Kruskal's Algorithm. Since there are 5 vertices (A, B, C, D, E), the Minimum Spanning Tree must have exactly 4 edges.
1. List all edges sorted by weight: AB(1), DE(2), BE(3), BD(4), BC(5), CE(6), AC(7).
2. Select edges without forming cycles:
Select AB (1).
Select DE (2).
Select BE (3). This connects the components {A,B} and {D,E}.
Skip BD (4) as it creates a cycle with BE and DE.
Select BC (5) to connect vertex C.
Total Weight: 1 + 2 + 3 + 5 = 11. Number of Edges: 4.