The Route Inspection (Chinese Postman) problem

The Route Inspection (Chinese Postman) problem Flashcards

Spec 3.1 · Edexcel A-Level Further 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 problem?
Finding the shortest closed route that traverses every arc of a network at least once.
What is the degree of a vertex?
The number of arc-ends meeting at the vertex.
How many odd vertices can a network have?
An even number, because the degrees add up to twice the number of arcs.
When is a network Eulerian?
When every vertex has even degree.
Shortest route in an Eulerian network?
The total weight of all the arcs, with no repeats.
Step 1 of the Route Inspection Algorithm?
Identify all the odd vertices.
How many pairings are there for 2 odd vertices?
One.
How many pairings are there for 4 odd vertices?
Three.
What is added to the total weight?
The least total for a pairing, using the shortest path for each pair.
Why is the direct arc not always used?
An indirect path between the odd vertices can be shorter.
What must you do if an arc is added?
Recount the degrees, because the odd vertices may change.
What if the network has more than four odd vertices?
Extra information limits the pairings you need to consider.

Flashcards