Bounds for the travelling salesman problem

Bounds for the travelling salesman problem Test

Spec 3.3–4 · Edexcel International A Level 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

Edexcel International A Level Maths

Bounds for the travelling salesman problem

Total 27 marks

Name

Class

Date

  1. 1
    A complete network has five vertices PP, QQ, RR, SS and TT, with lengths PQ=14PQ=14, PR=10PR=10, PS=17PS=17, PT=9PT=9, QR=11QR=11, QS=8QS=8, QT=15QT=15, RS=12RS=12, RT=13RT=13 and ST=16ST=16.
    (a)
    The nearest neighbour algorithm is applied starting at QQ. Which tour is produced?
    [1 mark]
    • AQQ-RR-PP-TT-SS-QQ
    • BQQ-SS-PP-TT-RR-QQ
    • CQQ-PP-TT-RR-SS-QQ
    • DQQ-SS-RR-PP-TT-QQ
    (b)
    The tour from QQ in part (a) has length 5454. Which statement about the travelling salesman problem is correct?
    [1 mark]
    • AThe shortest tour has length exactly 5454
    • BThe shortest tour has length at most 5454
    • CThe shortest tour has length at least 5454
    • DEvery starting vertex gives a tour of length 5454
    (c)
    Apply the nearest neighbour algorithm starting at PP. Write down the tour and its length, and state what this tells you about the shortest tour.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    A complete network has five depots VV, WW, XX, YY and ZZ, with lengths VW=11VW=11, VX=7VX=7, VY=9VY=9, VZ=14VZ=14, WX=6WX=6, WY=13WY=13, WZ=10WZ=10, XY=8XY=8, XZ=12XZ=12 and YZ=15YZ=15. A lower bound for the travelling salesman problem is found by deleting vertex VV.
    (a)
    What is the total length of a minimum spanning tree of the network with VV deleted?
    [1 mark]
    • A2424
    • B2626
    • C3434
    • D4040
    (b)
    Which two arcs at VV are added to the minimum spanning tree to form the lower bound?
    [1 mark]
    • AVZVZ and VWVW
    • BVXVX and VWVW
    • CVXVX and VYVY
    • DVYVY and VZVZ
    (c)
    Find the lower bound for the length of the shortest tour from deleting VV, and explain why it is a lower bound.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    A delivery firm has five depots AA to EE. The only direct roads and their lengths in km are AB=7AB=7, BC=5BC=5, CD=6CD=6, DE=4DE=4 and BE=9BE=9. A driver must visit every depot and return to the start, and may pass through a depot more than once.
    (a)
    Find the shortest distances between AA and DD, between BB and DD, and between CC and EE.
    [3 marks]
    (b)
    The shortest distances are AB=7AB=7, AC=12AC=12, AD=18AD=18, AE=16AE=16, BC=5BC=5, BD=11BD=11, BE=9BE=9, CD=6CD=6, CE=10CE=10 and DE=4DE=4. Apply the nearest neighbour algorithm to this complete network starting at AA, to find an upper bound. Give the route that the driver takes in the original network.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    A complete network has five vertices AA, BB, CC, DD and EE, with lengths AB=12AB=12, AC=9AC=9, AD=15AD=15, AE=7AE=7, BC=8BC=8, BD=11BD=11, BE=14BE=14, CD=10CD=10, CE=13CE=13 and DE=6DE=6.
    (a)
    (i) Use Kruskal's algorithm to find a minimum spanning tree and its weight.
    (ii) Hence find an upper bound by walking around the tree, and use shortcuts to improve this bound.
    [6 marks]
    (b)
    Find a lower bound by deleting BB. Hence show that the shortest tour has length 4141.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests