3D.3.1 The route inspection (Chinese postman) algorithm Quiz: Pearson Edexcel Further Maths, Unit 37

The 20 questions

1. The route inspection problem asks for a route that

   • traverses every edge at least once and returns to its start, with minimum total length
   • visits every vertex exactly once
   • finds the longest possible walk
   • uses every edge exactly once

2. In this specification, what is the most odd vertices a route inspection network can contain?

   • four
   • six
   • two
   • eight

3. If a network is Eulerian, the minimum length of a route inspection is

   • the total weight minus the largest edge
   • twice the total weight
   • the total weight of all its edges
   • the shortest path between two vertices

4. Odd vertices in a route inspection problem are dealt with by

   • adding new vertices
   • deleting edges between them
   • pairing only adjacent odd vertices
   • repeating shortest paths that pair them up, so every vertex ends with even degree

5. Repeated edges in a route inspection solution are added so that

   • every vertex has even degree
   • the route visits each vertex exactly once
   • they are removed from the network
   • their weights are doubled

6. A route inspection route starts and ends at

   • two different odd vertices
   • the same vertex
   • the vertex with the smallest edge weight
   • the vertex with the largest degree

7. How many ways are there to pair up 4 odd vertices?

   • 3
   • 8
   • 4
   • 6

8. A network has exactly two odd vertices, and the shortest path between them has length 3. The total weight of all edges is 20. What is the minimum route inspection length?

   • 17
   • 26
   • 20
   • 23

9. Four odd vertices A, B, C and D have shortest path lengths AB 2, CD 3, AC 5, BD 4, AD 6 and BC 7. What is the minimum total length of the repeated paths?

   • 5
   • 13
   • 3
   • 9

10. A network has total edge weight 30. Its odd vertices can be paired with repeats totalling 5. What is the minimum route length?

    • 25
    • 40
    • 35
    • 30

11. A network is Eulerian with total edge weight 18. What is the minimum route inspection length?

    • 9
    • 18
    • 36
    • 20

12. A network with four odd vertices has pairing totals 7, 9 and 11, and total edge weight 25. What is the minimum route length?

    • 36
    • 30
    • 34
    • 32

13. A network has total edge weight 44, and the shortest repeats needed to pair its odd vertices total 7. What is the minimum route length?

    • 56
    • 47
    • 37
    • 51

14. Odd vertices P, Q, R and S have pair distances PQ 4, RS 4, PR 10, QS 10, PS 3 and QR 2. What is the minimum total repeat length?

    • 20
    • 3
    • 8
    • 5

15. A route inspection on a network of total weight 42 has length 50. What repeat length was needed?

    • 8
    • 42
    • 92
    • 50

16. Four odd vertices P, Q, R and S have pair distances PQ 3, RS 3, PR 6, QS 2, PS 4 and QR 5. What is the minimum total repeat length?

    • 5
    • 9
    • 8
    • 6

17. Why can't the postman simply repeat the shortest single edge between two odd vertices?

    • all edge weights are equal
    • edges cannot be repeated at all
    • Repeats must make every vertex have even degree, so they must link all the odd vertices in pairs
    • the postman must visit every vertex exactly once

18. Why is the augmented network Eulerian once the odd vertices are paired by repeats?

    • it has become a tree
    • all edges now have equal weight
    • every vertex now has even degree and the network is connected
    • it has exactly two odd vertices

19. A network has total weight 60 and a minimum pairing repeat of 12. The route must start and end at A. What is its length?

    • 84
    • 72
    • 48
    • 60

20. A postman's route must start and end at the same vertex. The network has total weight 45 and the minimum repeats total 10. What is the route length?

    • 50
    • 55
    • 65
    • 45

Related quizzes

• Travelling salesman problems Quiz · 3D.3.2 · 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