What is the minimum cost of the spanning tree of the given graph?
2023
What is the minimum cost of the spanning tree of the given graph?
Answer: D. 14 — Concept — A spanning tree of a connected graph on n vertices is a cycle-free subgraph that keeps every vertex connected, and it always uses exactly n − 1…
- A.
12
- B.
13
- C.
11
- D.
14
Attempted by 120 students.
Show answer & explanation
Correct answer: D
Concept — A spanning tree of a connected graph on n vertices is a cycle-free subgraph that keeps every vertex connected, and it always uses exactly n − 1 edges. Among all such trees, the minimum spanning tree is the one whose edge weights add up to the smallest total. Kruskal's algorithm builds it greedily: sort all edges by non-decreasing weight and accept an edge only when its two endpoints currently lie in different components; an edge whose endpoints are already joined would close a cycle and is rejected.
Application — The figure has 8 vertices (A to H) and 11 weighted edges, so any spanning tree of it must contain exactly 8 − 1 = 7 edges. Listing the edges in non-decreasing order of weight:
Edge | Weight |
|---|---|
B–D | 1 |
G–H | 1 |
A–F | 2 |
B–C | 2 |
F–G | 2 |
A–B | 3 |
C–H | 3 |
E–G | 3 |
D–E | 4 |
C–E | 5 |
E–H | 6 |
Applying Kruskal's rule to that sorted list:
B–D (1): B and D lie in different components, so this edge is accepted.
G–H (1): G and H lie in different components, so this edge is accepted.
A–F (2): A and F lie in different components, so this edge is accepted.
B–C (2): C joins the component {B, D}, so this edge is accepted.
F–G (2): the component {A, F} merges with {G, H}, so this edge is accepted.
A–B (3): the component {A, F, G, H} merges with {B, C, D}, so this edge is accepted. Six edges are now in place, with a running total of 1 + 1 + 2 + 2 + 2 + 3 = 11.
C–H (3): C and H already lie in the same component, so this edge would close a cycle and is rejected.
E–G (3): E is still isolated, so this edge is accepted. It is the seventh edge, and the total becomes 11 + 3 = 14.
D–E (4), C–E (5) and E–H (6): all eight vertices are already connected by seven edges, so none of these is needed.
Cross-check — Prim's algorithm started from A selects A–F (2), F–G (2), G–H (1), A–B (3), B–D (1), B–C (2) and E–G (3) — the same seven edges, with the same total 2 + 2 + 1 + 3 + 1 + 2 + 3 = 14. A lower bound agrees: the seven smallest edge weights anywhere in the figure are 1, 1, 2, 2, 2, 3 and 3, which already add to 14, so no seven-edge subgraph of this graph can cost less than 14.
Result — The minimum cost of a spanning tree of the given graph is 14.