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 type of cycle does the travelling salesperson problem aim to find with minimum total weight?

    • Maximum spanning tree
    • Minimum Eulerian cycle
    • Minimum Hamiltonian cycle
    • Shortest path tree

  2. Which algorithm produces a lower bound for the travelling salesperson problem?

    • Deleted node MST
    • Chinese postman algorithm
    • Dijkstra's algorithm
    • Nearest neighbour algorithm

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

    • Nearest neighbour algorithm
    • Kruskal's algorithm
    • Prim's algorithm
    • Deleted node MST

  4. A TSP network has lower bound 18 and upper bound 20. What is the range for the optimal weight?

    • At least 20
    • At most 18
    • 18 to 20
    • Greater than 20

  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. Removing one node and its two connected tour arcs leaves which structure on the remaining nodes?

    • Complete graph
    • Bipartite graph
    • Spanning tree
    • Hamiltonian cycle

  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. How can the upper bound from the nearest neighbour algorithm be improved for a TSP?

    • Delete multiple nodes
    • Reverse arc directions
    • Remove longest edges
    • Try different starts

  11. A new arc is added to a TSP network model. How does the optimal tour weight change?

    • Always decreases
    • Decreases or unchanged
    • Increases or unchanged
    • Always increases

  12. How is a one-way street represented when refining a network model?

    • Loop arc
    • Undirected edge
    • Dummy node
    • Directed arc

  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 TSP lower bound is 31 and upper bound is 38. What is the gap between these bounds?

    • 12
    • 35
    • 69
    • 7

  15. To account for varying traffic levels during the day, how should arc weights be refined?

    • Time-dependent weights
    • Zero weights
    • Negative weights
    • Constant weights

  16. Why is a TSP tour impossible in a network containing a node of degree 1?

    • Requires degree zero
    • Requires odd degree
    • Requires degree two
    • Requires degree three

  17. Why can the deleted node MST lower bound be strictly less than the optimal TSP tour weight?

    • Contains negative weights
    • Not a tour
    • Exceeds max capacity
    • Has disconnected nodes

  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. What primary benefit do lower and upper bounds provide for a TSP problem?

    • Calculate exact weight
    • Eliminate all nodes
    • Guarantee unique route
    • Bracket optimal weight

  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