D2 June 2008 Q7
7.
The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.
(a) Obtain a minimum spanning tree for the network using Kruskal’s algorithm, stating the order in which you select the arcs. (2)
(b) Use your answer to part (a) to determine an initial upper bound for the length of the route. (1)
(c) Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km. State the corresponding route. (4)
(d) Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route. (3)
(e) By deleting C, and all of its arcs, find a lower bound for the length of the route. (4)
(f) Use your results to write down the smallest interval which you are confident contains the optimal length of the route. (2)
| Scheme | Marks |
|---|---|
| GH(38) GF(56) CA(57) EC(59) FE(61) CD(64) CB(68) | M1 A1ft |
| (2) |
| Scheme | Marks |
|---|---|
| \(2 \times 403 = 806\) (km) | B1 |
| (1) |
| Scheme | Marks |
|---|---|
| e.g. DH saves 167 AB saves 23 | M1 A1 |
| \(806 - 190 = 616\) (km) | A1 |
 | A1 |
| (4) |
Notes
The route “A B C E F G H D C A” is printed at the start of part (d) in the scheme; it is the route for this part (length 616).
| Scheme | Marks |
|---|---|
| B C A E F G H D B \(68 + 57 + 98 + 61 + 56 + 38 + 111 + 108 = 597\) (km) | M1 A1 A1 |
| (3) |
| Scheme | Marks |
|---|---|
Delete C  | M1 A1 M1 A1ft |
| RMST weight = 444 Lower bound \(= 444 + 59 + 57 = 560\) (km) | |
| (4) |
Notes
The scheme prints the (f) label against these two lines; they complete part (e).
| Scheme | Marks |
|---|---|
| \(560 \lt \text{length} \leqslant 597\) | B2, 1, 0 |
| (2) | |
| (16 marks) |