Route inspection and travelling salesperson

Route inspection and travelling salesperson Test

Spec DB3–DB4 · AQA A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

AQA A-Level Further Maths

Route inspection and travelling salesperson

Total 27 marks

Name

Class

Date

  1. 1
    A network has six nodes AA to FF. The arcs and their weights, in km, are ABAB 6, ACAC 5, BCBC 4, BDBD 7, CDCD 3, CECE 8, DEDE 6, DFDF 9 and EFEF 5. The total weight of all the arcs is 53 km.
    (a)
    Which nodes have odd degree?
    [1 mark]
    • ABB and CC
    • BBB and EE
    • CAA and FF
    • DCC and DD
    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]
    • A5353 km
    • B6666 km
    • C6565 km
    • D1212 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 (BB and EE), in either order
    B1: length 53 km, as every arc can be used exactly once

    Total for question 1: 4 marks

  2. 2
    A van starts at depot AA, must visit each of depots BB, CC, DD and EE exactly once and return to AA. The distances in km between each pair of depots are ABAB 8, ACAC 5, ADAD 6, AEAE 14, BCBC 11, BDBD 9, BEBE 4, CDCD 12, CECE 13 and DEDE 15.
    (a)
    The nearest neighbour algorithm is applied starting at AA. What is the length of the tour it produces?
    [1 mark]
    • A3636 km
    • B3737 km
    • C4343 km
    • D4141 km
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    Delete vertex DD and use the remaining vertices to find a lower bound for the length of the shortest tour. What is it?
    [1 mark]
    • A3232 km
    • B1717 km
    • C2323 km
    • D3636 km
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Delete vertex BB 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 A,C,D,EA,C,D,E is ACAC 5, ADAD 6, CECE 13 (24); add the two shortest arcs at BB, BEBE 4 and ABAB 8, giving 3636
    A1:
    36≤36\le shortest tour ≤41\le41

    Total for question 2: 4 marks

  3. 3
    A courier based at AA must deliver parcels to BB, CC and DD and return to AA, visiting each at least once. The roads, with lengths in km, are ABAB 4, BCBC 3, CDCD 5, DADA 6 and BDBD 9.
    (a)
    Show that the shortest distance from BB to DD is 8 km, and find the shortest distance from AA to CC.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: compare the direct road BDBD (9) with B,C,DB,C,D (3+53+5)
    A1: shortest
    BB to DD is 8 km
    B1: shortest
    AA to CC is 7 km, via BB (4+34+3), as A,D,CA,D,C is 11
    (b)
    Using the shortest distances between AA, BB, CC and DD, find the shortest route for the courier and state its length.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: consider tours of AA, BB, CC, DD using shortest distances (ABAB 4, ACAC 7, ADAD 6, BCBC 3, BDBD 8, CDCD 5)
    A1:
    A,B,C,D,AA,B,C,D,A is 4+3+5+6=184+3+5+6=18 km
    A1: the other two tours,
    A,B,D,C,AA,B,D,C,A and A,C,B,D,AA,C,B,D,A, are each 24 km
    B1: shortest route
    A,B,C,D,AA,B,C,D,A (or the reverse), 18 km
    Accept: other equivalent notation for the same route

    Total for question 3: 7 marks

  4. 4
    A council inspects every road in a village. The roads, with their lengths in km, are ABAB 8, ACAC 5, AFAF 10, BCBC 6, BDBD 9, CDCD 7, CECE 9, DEDE 4, DFDF 6 and EFEF 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 AA, BB, EE, FF
    B1: shortest distances between them:
    ABAB 8, EFEF 7, AFAF 10, AEAE 14 (via CC), BEBE 13 (via DD), BFBF 15 (via DD)
    M1: the three pairings of the odd nodes are
    ABAB & EFEF, AEAE & BFBF, AFAF & BEBE
    A1: totals
    1515, 2929, 2323
    B1: repeat the shortest pairing,
    ABAB and EFEF (15)
    A1: length
    71+15=8671+15=86 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
    EFEF (7), so repeat EFEF and start and finish at AA and BB (either order)
    A1: length
    71+7=7871+7=78 km
    B1: this saves 8 km compared with the closed route of 86 km

    R1: driving back from
    BB to AA 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
    BB is suitable (for example for collection)

    Total for question 4: 12 marks

End of questions

Subtopic tests