Lesson DB4-DB5

DB4-DB5 Travelling salesperson bounds and refining network models Quiz: AQA Further Maths, Unit 5

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson DB4-DB5, Travelling salesperson bounds and refining network models: 20 multiple choice questions for the AQA Further Maths (7367), Unit 5: Optional application 3: discrete mathematics, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. What is the travelling salesperson problem (TSP) on a network?

    • Finding a route that traverses every arc at least once, repeating arcs if needed
    • Finding a minimum spanning tree that connects every node to the network
    • Finding a minimum-weight closed route that visits every node exactly once and returns to the start
    • Finding the route of maximum total weight through the network

  2. Which method gives a lower bound for the travelling salesperson problem?

    • Delete one node, find a minimum spanning tree of the remaining nodes, then add the two smallest arcs from the deleted node
    • Find a Hamiltonian cycle that uses only the greatest-weight arc at each node
    • Add the two largest arcs from the start node to a minimum spanning tree
    • Find a minimum spanning tree and double its total weight

  3. Which method gives an upper bound for the travelling salesperson problem?

    • Start at a node and repeatedly move to the nearest unvisited node, then return to the start
    • Choose the shortest arc in the network and repeat it until every node has been visited
    • Delete each node in turn and find a minimum spanning tree of the remaining network
    • Start at the node of greatest degree and always move along the longest arc available

  4. A network's lower bound for the travelling salesperson problem is 18, and a nearest neighbour tour has weight 20. What can be said about the optimal tour weight?

    • It is exactly 19
    • It is at least 20
    • It lies between 18 and 20 inclusive
    • It is at most 18

  5. A complete network has nodes A, B, C, D, E with arc weights AB=4, AC=6, AD=5, AE=7, BC=3, BD=8, BE=6, CD=4, CE=5 and DE=2. Deleting node A leaves nodes B, C, D and E, whose minimum spanning tree has weight 9. What is the lower bound for the travelling salesperson problem?

    • 20
    • 9
    • 18
    • 13

  6. A complete network has nodes A, B, C, D, E with arc weights AB=4, AC=6, AD=5, AE=7, BC=3, BD=8, BE=6, CD=4, CE=5 and DE=2. Using the nearest neighbour method starting at A, the tour is A-B-C-D-E-A. What is its total weight?

    • 18
    • 19
    • 20
    • 22

  7. A complete network has nodes A, B, C, D, E with arc weights AB=4, AC=6, AD=5, AE=7, BC=3, BD=8, BE=6, CD=4, CE=5 and DE=2. What is the total weight of the tour A-B-C-E-D-A?

    • 21
    • 19
    • 20
    • 18

  8. Why is the lower bound method valid for the travelling salesperson problem?

    • A minimum spanning tree is itself a tour, so its weight equals the travelling salesperson optimum
    • The lower bound uses the largest arcs, which must be included in every tour
    • A tour minus one node's two arcs is a spanning tree of the others, so the tour weighs at least the MST plus the two smallest arcs
    • A Hamiltonian cycle always has the same weight as the minimum spanning tree of the network

  9. How many distinct Hamiltonian cycles does a complete network on 6 nodes have, treating a cycle and its reverse as the same?

    • 720
    • 60
    • 30
    • 120

  10. Which approach improves an upper bound for the travelling salesperson problem found by the nearest neighbour method?

    • Use the maximum-weight arc at each step to avoid short cycles
    • Delete the node with the fewest arcs and repeat the method on the rest
    • Replace every arc weight with its reciprocal and repeat the method
    • Repeat the nearest neighbour method from different starting nodes and keep the tour of least weight

  11. A network model is refined by adding a new arc between two nodes that were not previously joined. What is the effect on the optimal travelling salesperson tour?

    • The new arc always becomes part of the minimum spanning tree and must be deleted
    • The optimal tour weight can stay the same or fall, but cannot rise, because more routes become available
    • The optimal tour weight always rises, because the network is larger
    • The optimal tour weight never changes, because tours use only existing arcs

  12. In a refined network model, how is a one-way street best represented?

    • By doubling the weight of every arc that joins the street's two ends
    • By two undirected arcs of equal weight
    • By removing the node at the end of the street from the network
    • By a directed arc, so that travel is allowed only in the permitted direction

  13. If deleting a node gives a minimum spanning tree of weight W on the remaining nodes, and the two smallest arcs at the deleted node have weights a and b, what is the lower bound for the travelling salesperson problem?

    • W + a + b
    • 2W + a + b
    • W + a - b
    • W + 2a + 2b

  14. A travelling salesperson problem has lower bound 31 and a nearest neighbour tour of weight 38. Which statement is correct?

    • The gap between the bounds is 69, found by adding the lower and upper bounds
    • The optimal tour weight is at most 31, because the lower bound is an upper bound
    • The optimal tour weight is exactly 38, because nearest neighbour is always optimal
    • The optimal tour weight lies between 31 and 38, so the gap between the bounds is 7

  15. A road network model assumes fixed travel times, but traffic varies during the day. Which refinement is valid?

    • Replace the fixed arc weights with time-dependent weights reflecting traffic at the relevant time of day
    • Ignore every node of degree 2, since it does not affect the route
    • Use the average of all arc weights for every arc in the network
    • Remove every arc except those on a minimum spanning tree

  16. A node in a network has degree 1. What does this imply for the travelling salesperson problem?

    • The minimum spanning tree must exclude this node
    • The nearest neighbour tour must use this node twice
    • No Hamiltonian cycle exists, because a tour must use two different arcs at every node
    • The lower bound must be zero, since the node adds no weight

  17. Why might the lower bound for the travelling salesperson problem be strictly less than the optimal tour weight?

    • The bound always uses an arc counted twice, which inflates the optimum
    • The bound comes from a relaxed problem, so it need not correspond to any actual tour
    • The bound is always the weight of a Hamiltonian cycle that is not optimal
    • The bound is always greater than the optimum, so it can never be strictly less

  18. A complete network has nodes A, B, C, D, E with arc weights AB=4, AC=6, AD=5, AE=7, BC=3, BD=8, BE=6, CD=4, CE=5 and DE=2. Using the nearest neighbour method starting at C, the tour found is C-B-A-D-E-C. What is its total weight?

    • 18
    • 22
    • 19
    • 20

  19. Which statement best describes the role of the lower and upper bounds for the travelling salesperson problem?

    • They guarantee that the nearest neighbour tour is the optimal tour
    • They remove the need to calculate any tour at all
    • They show that the lower bound is always exactly the optimum
    • They show how close a found tour is to optimal, since the true optimum lies between the lower and upper bounds

  20. How many distinct Hamiltonian cycles does a complete network on 5 nodes have, treating a cycle and its reverse as the same?

    • 120
    • 24
    • 6
    • 12

All AQA Further Maths quizzes