What is the order of a vertex?

The number of arcs meeting at the vertex.

How many odd vertices can a network have?

An even number: 0, 2, 4, and so on.

If all vertices are even, what is the shortest route length?

The total weight of all the arcs.

How do you handle odd vertices?

Pair them up, find the shortest path in each pair, and choose the pairing with the least total.

How is the shortest route length found?

The total weight of the arcs plus the least pairing total.

Which arcs are travelled twice?

The arcs on the shortest paths of the chosen pairing.

Why must you check shortest paths between odd vertices?

A path through other vertices can be shorter than the direct arc.

A new arc joins two odd vertices. What happens to the odd vertices?

Both become even, so there are two fewer odd vertices.

The route inspection problemEdexcel International A Level Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is the route inspection (Chinese postman) problem?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What is the route inspection (Chinese postman) problem?: Find the shortest closed route that travels along every arc at least once.
What is the order of a vertex?: The number of arcs meeting at the vertex.
What is an odd vertex?: A vertex with an odd order.
How many odd vertices can a network have?: An even number: $0$ , $2$ , $4$ , and so on.
If all vertices are even, what is the shortest route length?: The total weight of all the arcs.
How do you handle odd vertices?: Pair them up, find the shortest path in each pair, and choose the pairing with the least total.
How many pairings are there for 2 odd vertices?: $1$ .
How many pairings are there for 4 odd vertices?: $3$ .
How is the shortest route length found?: The total weight of the arcs plus the least pairing total.
Which arcs are travelled twice?: The arcs on the shortest paths of the chosen pairing.
Why must you check shortest paths between odd vertices?: A path through other vertices can be shorter than the direct arc.
A new arc joins two odd vertices. What happens to the odd vertices?: Both become even, so there are two fewer odd vertices.

Exam questions on The route inspection problem

A street cleaner must travel along every street in a small town, starting and finishing at the same junction. The junctions are $A$ , $B$ , $C$ , $D$ and $E$ , and the streets and their lengths in hundreds of metres are $AB=5$ , $AC=8$ , $BC=4$ , $BD=7$ , $CD=6$ , $CE=9$ and $DE=3$ .
Find the length of the shortest route that the cleaner can take.2 marks
A network has four vertices $W$ , $X$ , $Y$ and $Z$ , and every pair of vertices is joined by an arc. The lengths are $WX=6$ , $WY=9$ , $WZ=8$ , $XY=7$ , $XZ=10$ and $YZ=5$ . A route must traverse every arc at least once, starting and finishing at $W$ .
Find the length of the shortest route.2 marks
A gritting lorry must travel along every road in a village at least once, starting and finishing at the depot $A$ . The junctions are $A$ , $B$ , $C$ , $D$ and $E$ , and the roads and their lengths in km are $AB=2$ , $AC=3$ , $BC=13$ , $BD=8$ , $CD=5$ , $CE=4$ , $DE=11$ and $AE=10$ .
List the odd vertices. Find the three ways of pairing them, and the total length of the shortest connections for each pairing.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).