Least distances between five campsites
Figure 1 shows the footpaths between five campsites, , , , and , in a national park. The number on each arc is the length, in km, of the footpath.
A ranger wants to plan a tour that visits every campsite, so she first converts the network into a complete network of least distances.
(a) Complete a table showing the least distance, in km, between every pair of campsites. (3)
(b) Explain why the entry for to in your table is not , referring to the triangle inequality. (1)
- 1
(a) Compare each direct footpath with the routes through other campsites. to direct is but is ; to direct is but is . Pairs with no direct path need a route: by , by , by . M1
- 2
The remaining direct paths are already least: , , , , . A1
- 3
The complete table of least distances (km), symmetric about the diagonal: A1
A B C D E A – 6 4 11 9 B 6 – 2 6 7 C 4 2 – 7 5 D 11 6 7 – 2 E 9 7 5 2 – - 4
(b) The triangle inequality requires . The path lengths give , so the direct path breaks it; the least distance is used instead, and the completed table does satisfy the triangle inequality. B1
Answer
(a) , , , , , , , , , (b) , so the direct path breaks the triangle inequality; the least distance (via ) is entered
Examiner tip
M1 needs at least six correct entries; the first A1 is lost most often by copying the direct lengths for and for into the table without checking the two-step routes. Check every pair, including pairs that already have a direct arc. In (b) quote the inequality with the actual numbers; "it is shorter to go round" with no reference to , and scores B0.