The Travelling Salesman problem

The Travelling Salesman problem Quiz

Spec 3.2 · Edexcel A-Level Further Maths: Quiz

Studying this course? Keep your progress in one place.

Pick an answer for each. Quizzes never use energy.

5 questions, one answer each

Each answer is checked as you go, with why.

See all 5 questions

  1. 1. Which statement does NOT apply to the classical Travelling Salesman problem?

    • A. The network is complete
    • B. Arcs may be used more than once
    • C. The triangle inequality holds
    • D. Each vertex is visited exactly once

  2. 2. A minimum spanning tree has weight 40. What upper bound does doubling give?

    • A. 20
    • B. 40
    • C. 60
    • D. 80

  3. 3. Deleting vertex X leaves a minimum spanning tree of weight 30. The two shortest arcs at X are 5 and 7. What is the lower bound?

    • A. 42
    • B. 30
    • C. 35
    • D. 37

  4. 4. A lower bound is 52 and the best upper bound found is a tour of length 55. Between which values must the shortest tour lie?

    • A. 52 and 58
    • B. 55 and 58
    • C. 52 and 55
    • D. 52 and 53

  5. 5. Why can shortcuts improve an upper bound?

    • A. They lower the lower bound
    • B. By the triangle inequality, a direct arc is no longer than the route it replaces
    • C. They find a minimum spanning tree
    • D. They make the network complete

Quiz