D2 June 2012 Q2
2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | - | 16 | 25 | 21 | 12 | 15 |
| B | 16 | - | 24 | 22 | 21 | 12 |
| C | 25 | 24 | - | 18 | 30 | 27 |
| D | 21 | 22 | 18 | - | 15 | 12 |
| E | 12 | 21 | 30 | 15 | - | 18 |
| F | 15 | 12 | 27 | 12 | 18 | - |
Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.
(a) Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of Toby’s route. (3)
(b) Starting by deleting A, and all of its arcs, find a lower bound for the route length. (4)
| Scheme | Marks |
|---|---|
| A E D F B C A 12 15 12 12 24 25 = 100 km | 1M1 1A1 2A1 |
| (3) |
Notes
a1M1 NN Each vertex visited at least once, accept 156324 across top of table (condone lack of return to start).
a1A1 Route CAO must be stated, must return to A, accept link back to A.
a2A1 Length CAO 100. Do not ISW if candidates then go on to double the route length.
| Scheme | Marks |
|---|---|
Delete A | 1M1 1A1 |
| RMST weight = 12 + 12 + 15 + 18 = 57 (km) Lower bound = 57 + 12 + 15 = 84 (km) | 2M1 2A1 |
| (4) | |
| (7 marks) |
Notes
b1M1 Finding correct RMST (maybe implicit) 57 sufficient; or 12, 12, 15 and 18. Must have 4 arcs.
b1A1 CAO; tree or list of arcs or 57 or 12 + 12 + 15 + 18 seen.
b2M1 Adding 2 least arcs from A to ‘tree’; 12 and 15 or AF and AE or 27 only. Must add these arcs distinctly.
b2A1 CAO 84