AQA A-Level Further Maths
Route inspection and travelling salesperson
Total 27 marks
Name
Class
Date
- 1A network has six nodes to . The arcs and their weights, in km, are 6, 5, 4, 7, 3, 8, 6, 9 and 5. The total weight of all the arcs is 53 km.(a)Which nodes have odd degree?[1 mark]
- A and
- B and
- C and
- D and
Show the mark scheme
Mark scheme
Answer: B(b)What is the length of the shortest closed route that traverses every arc at least once?[1 mark]- A km
- B km
- C km
- D km
Show the mark scheme
Mark scheme
Answer: C(c)The route may now start and finish at different nodes. State where it should start and finish and the length of the shortest such route that traverses every arc at least once.[2 marks]Show the mark scheme
Mark scheme
B1: start at one odd node and finish at the other ( and ), in either order
B1: length 53 km, as every arc can be used exactly onceTotal for question 1: 4 marks
- 2A van starts at depot , must visit each of depots , , and exactly once and return to . The distances in km between each pair of depots are 8, 5, 6, 14, 11, 9, 4, 12, 13 and 15.(a)The nearest neighbour algorithm is applied starting at . What is the length of the tour it produces?[1 mark]
- A km
- B km
- C km
- D km
Show the mark scheme
Mark scheme
Answer: D(b)Delete vertex and use the remaining vertices to find a lower bound for the length of the shortest tour. What is it?[1 mark]- A km
- B km
- C km
- D km
Show the mark scheme
Mark scheme
Answer: A(c)Delete vertex instead, to find a lower bound. Use it, with your answer to part (a), to write down an interval for the length of the shortest tour.[2 marks]Show the mark scheme
Mark scheme
M1: minimum spanning tree of is 5, 6, 13 (24); add the two shortest arcs at , 4 and 8, giving
A1: shortest tourTotal for question 2: 4 marks
- 3A courier based at must deliver parcels to , and and return to , visiting each at least once. The roads, with lengths in km, are 4, 3, 5, 6 and 9.(a)Show that the shortest distance from to is 8 km, and find the shortest distance from to .[3 marks]
Show the mark scheme
Mark scheme
M1: compare the direct road (9) with ()
A1: shortest to is 8 km
B1: shortest to is 7 km, via (), as is 11(b)Using the shortest distances between , , and , find the shortest route for the courier and state its length.[4 marks]Show the mark scheme
Mark scheme
M1: consider tours of , , , using shortest distances ( 4, 7, 6, 3, 8, 5)
A1: is km
A1: the other two tours, and , are each 24 km
B1: shortest route (or the reverse), 18 km
Accept: other equivalent notation for the same routeTotal for question 3: 7 marks
- 4A council inspects every road in a village. The roads, with their lengths in km, are 8, 5, 10, 6, 9, 7, 9, 4, 6 and 7. The total length of all the roads is 71 km. The inspector must travel along every road at least once.(a)Find the length of the shortest route that starts and finishes at the same point and inspects every road. Show your working.[6 marks]
Show the mark scheme
Mark scheme
B1: the nodes of odd degree are , , ,
B1: shortest distances between them: 8, 7, 10, 14 (via ), 13 (via ), 15 (via )
M1: the three pairings of the odd nodes are & , & , &
A1: totals , ,
B1: repeat the shortest pairing, and (15)
A1: length km(b)The inspector no longer needs to finish where they started. State where the inspector should start and finish and the length of the shortest route. Evaluate whether this is worthwhile if the inspector must be driven back to the starting point afterwards.[6 marks]Show the mark scheme
Mark scheme
M1: start and finish at two of the odd nodes and repeat only the shortest path between the other two
B1: the smallest distance between two odd nodes is (7), so repeat and start and finish at and (either order)
A1: length km
B1: this saves 8 km compared with the closed route of 86 km
R1: driving back from to is 8 km, so the total is again 86 km and there is no saving
R1: it is only worthwhile if the inspector does not need to return to the start, or if the finishing point is suitable (for example for collection)Total for question 4: 12 marks
End of questions