The travelling salesman problem

The travelling salesman problem Quiz

Spec 3.2 · Edexcel International A Level 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 is true of a tour?

    • A. It visits every vertex and returns to the start
    • B. It visits every arc once
    • C. It visits each vertex exactly once and need not return
    • D. It is the shortest path between two vertices

  2. 2. How many different tours are there on a complete graph with 55 vertices, counting a tour and its reverse as one?

    • A. 55
    • B. 1212
    • C. 2424
    • D. 6060

  3. 3. A tree has arcs of total weight 1818. What is the shortest tour that visits every vertex?

    • A. 1818
    • B. 99
    • C. 2727
    • D. 3636

  4. 4. In a triangle with sides 66, 99 and 1414, is the triangle inequality satisfied?

    • A. No, because 14>6+914>6+9
    • B. Yes, because 14>914>9
    • C. Yes, because 14<6+914<6+9
    • D. No, because 9>69>6

  5. 5. Which network has no classical TSP solution?

    • A. A complete network on four vertices
    • B. A cycle through all the vertices
    • C. One with a vertex joined to only one other vertex
    • D. A complete network on five vertices

Quiz