The route inspection 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 (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: , , , 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?
- .
- How many pairings are there for 4 odd vertices?
- .
- 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.