The route inspection problem

The route inspection problem Flashcards

Spec 3.1 · Edexcel International A Level Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

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: 00, 22, 44, 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?
11.
How many pairings are there for 4 odd vertices?
33.
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.

Flashcards