The Route Inspection (Chinese Postman) problem 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.