IB Mathematics AHL 3.16 Walks, trails, paths, circuits, cycles AI HL Paper 2- Exam Style Questions- New Syllabus
A hygiene inspector, based in Town A, needs to visit restaurants in five towns (B, C, D, E, F) and return to Town A. The inspector must visit each town exactly once. The distances between the towns, in kilometers, are provided in the table below.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 31 | 28 | 26 | 22 | 23 | |
| B | 31 | 25 | 20 | 27 | 25 | |
| C | 28 | 25 | 19 | 22 | 24 | |
| D | 26 | 20 | 19 | 21 | 22 | |
| E | 22 | 27 | 22 | 21 | 24 | |
| F | 23 | 25 | 24 | 22 | 24 |
(a) Starting from Town A, apply the nearest neighbour algorithm to determine an upper bound for the total distance of the inspector’s journey. Specify the sequence of towns visited. [4 marks]
(b) By excluding Town A, use Prim’s algorithm starting at Town B to calculate a lower bound for the inspector’s journey distance. [5 marks]
(c) Using the minimum spanning tree from part (b), assess whether the lower bound represents a feasible journey for the inspector. [3 marks]
▶️ Answer/Explanation
(a) Using the nearest neighbour algorithm starting at A:
- From A: Nearest is E (22 km).
- From E: Nearest unvisited is D (21 km).
- From D: Nearest unvisited is C (19 km).
- From C: Nearest unvisited is F (24 km).
- From F: Nearest unvisited is B (25 km).
- From B: Return to A (31 km).
Order: A → E → D → C → F → B → A
Total distance: \( 22 + 21 + 19 + 24 + 25 + 31 = 142 \, \text{km} \)
\[ \boxed{\text{AEDCFBA}, \, 142 \, \text{km}} \]
(b) Apply Prim’s algorithm starting at B, excluding A:
Vertices: B, C, D, E, F
- Start at B. Nearest: D (20 km).
- From B, D: Nearest is C (from D, 19 km).
- From B, D, C: Nearest is E (from D, 21 km).
- From B, D, C, E: Nearest is F (from D, 22 km).
MST edges: BD (20), DC (19), DE (21), DF (22). Total MST weight: \( 20 + 19 + 21 + 22 = 82 \, \text{km} \).
Reconnect A using two shortest edges: AE (22), AF (23). Lower bound: \( 82 + 22 + 23 = 127 \, \text{km} \).
\[ \boxed{127 \, \text{km}} \]
(c) The MST (B, C, D, E, F) forms a tree with edges BD, DC, DE, DF. Reattaching A with edges AE and AF creates a graph with a cycle (e.g., A–E–D–C–A). A Hamiltonian cycle requires a single cycle without repeated edges, but this graph has degree 3 at D, making it impossible to form a valid tour without repeating edges or vertices. Thus, the lower bound of 127 km is not achievable.
\[ \boxed{\text{Not achievable}} \]