3D.3.2 Travelling salesman problems Quiz: Pearson Edexcel Further Maths, Unit 37

The 20 questions

1. How many times is each vertex visited in the classical travelling salesman problem?

   • At least twice
   • Once only
   • As needed
   • Twice

2. A walk that visits every vertex and returns to its starting vertex is called a

   • trail
   • cycle only
   • tour
   • path

3. For vertices A, B and C, what does the triangle inequality state about route lengths?

   • AB = AC + CB
   • AB >= AC + CB
   • AB > AC + CB
   • AB <= AC + CB

4. Which vertex does the nearest neighbour algorithm move to next?

   • Random unvisited vertex
   • Nearest unvisited vertex
   • Nearest visited vertex
   • Furthest unvisited vertex

5. What does the nearest neighbour algorithm provide for the optimal tour length?

   • Mean value
   • Lower bound
   • Upper bound
   • Exact value

6. What is the first step in finding a lower bound by removing a vertex in TSP?

   • Double all edges
   • Find tour length
   • Delete shortest edges
   • Find remaining MST

7. What effect does a shortcut have on total tour length when using the triangle inequality?

   • Never increases
   • Doubles length
   • Always decreases
   • Always increases

8. A triangle has sides 3, 4 and 5. What is the length of its only tour?

   • 12
   • 9
   • 8
   • 15

9. Vertices A, B, C and D have edges AB 2, AC 4, AD 3, BC 3, BD 5 and CD 2. The nearest neighbour tour starts at A. What is its length?

   • 12
   • 10
   • 11
   • 9

10. Which set of distances does NOT satisfy the triangle inequality?

    • AB = 4, AC = 4, CB = 4
    • AB = 6, AC = 3, CB = 3
    • AB = 7, AC = 3, CB = 3
    • AB = 5, AC = 3, CB = 4

11. A lower bound comes from removing vertex A, leaving a minimum spanning tree of weight 9 on the other vertices. A has edges of weight 3 and 4 to those vertices. What is the lower bound?

    • 12
    • 14
    • 18
    • 16

12. A classical tour visits 6 vertices, each once, and returns to its start. How many edges does the tour use?

    • 7
    • 6
    • 5
    • 12

13. Nearest neighbour gives an upper bound of 22 and lower bound is 18. What is optimal tour?

    • Between 18 and 22
    • Greater than 22
    • Exactly 22
    • Less than 18

14. In a complete network built from shortest distances, the direct distance A to C is 9, but the shortest route A to B to C has length 7. What weight does the complete network assign to A-C?

    • 9
    • 7
    • 3
    • 12

15. A minimum spanning tree of a network has weight 10. Under the triangle inequality, what upper bound does doubling this tree give for the classical tour?

    • 30
    • 20
    • 5
    • 10

16. An upper bound of 24 and a lower bound of 21 are found for a travelling salesman problem. What is the gap between them?

    • 5
    • 2
    • 26
    • 3

17. Why is the nearest neighbour algorithm not guaranteed to find the optimal travelling salesperson tour?

    • Subtours form
    • Early greedy choices
    • Negative edge weights
    • Too many vertices

18. In the removed-vertex lower bound argument for TSP, what does the remaining graph form?

    • Single path
    • Spanning tree
    • Eulerian cycle
    • Maximal matching

19. Doubling every edge of an MST and shortcutting gives what bound for TSP?

    • Zero bound
    • Exact optimum
    • Lower bound
    • Upper bound

20. A network has edges AB 4, AC 6, BC 3, CD 5 and BD 7. Removing vertex A, the minimum spanning tree of B, C and D has weight 8. What is the lower bound on the classical tour?

    • 14
    • 18
    • 17
    • 22

Related quizzes

• The route inspection (Chinese postman) algorithm Quiz · 3D.3.1 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions
• Goodness of fit tests for discrete distributions Quiz · 3B.6.1 · 20 questions