Question 1
Paper 2Medium6 marksA road-maintenance vehicle starts at depot A, must travel along every road segment at least once, and must return to A. The roads are undirected.
| Road | Length (km) | Road | Length (km) |
|---|---|---|---|
| AB | 4 | AC | 6 |
| AD | 8 | BC | 2 |
| BD | 5 | CD | 3 |
| CE | 7 | DE | 4 |
| DF | 6 | EF | 2 |
The following table gives the least distance, in kilometres, between each pair of locations.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | – | 4 | 6 | 8 | 12 | 14 |
| B | 4 | – | 2 | 5 | 9 | 11 |
| C | 6 | 2 | – | 3 | 7 | 9 |
| D | 8 | 5 | 3 | – | 4 | 6 |
| E | 12 | 9 | 7 | 4 | – | 2 |
| F | 14 | 11 | 9 | 6 | 2 | – |
(a)[1]
State all the locations of odd degree.
(b)[1]
Using the least-distance table, determine which pairs of odd-degree locations should have their shortest paths repeated to minimize the additional distance.
(c)[4]
Hence determine the minimum distance travelled. Explain why the Chinese postman algorithm is appropriate rather than the travelling salesman algorithm, and why the repetitions in part (b) allow the vehicle to return to A after traversing every road.