Route inspection & travelling salesman
Practice Flashcards
Flip to reveal answersWhat does the Chinese postman (route inspection) problem find?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 8 Flashcards — Route inspection & travelling salesman
Sign up free to track progress and get spaced-repetition review schedules.
Question
What does the Chinese postman (route inspection) problem find?
Answer
The shortest CLOSED walk that uses every EDGE at least once and returns to the start.
Question
When can the postman traverse every edge exactly once?
Answer
When every vertex has even degree (an Eulerian circuit exists); then the answer is just the sum of all edges.
Question
Route-inspection method with odd vertices?
Answer
Pair the odd-degree vertices so the total of the shortest paths between the pairs is least; add that to the sum of all edges.
Question
CPP length formula?
Answer
Sum of all edges + minimum pairing of the odd-degree vertices' shortest paths.
Question
What does the travelling salesman problem (TSP) find?
Answer
The shortest CLOSED route visiting every VERTEX exactly once and returning to the start (a Hamiltonian cycle).
Question
How do you get an upper bound for the TSP?
Answer
Nearest-neighbour algorithm: from the start, always go to the nearest unvisited vertex, then return to start. Its length is an upper bound.
Question
How do you get a lower bound for the TSP (deleted-vertex method)?
Answer
Delete a vertex; find the MST of the rest; add the two cheapest edges from the deleted vertex back.
Question
Edge problem or vertex problem?
Answer
Route inspection covers every EDGE; travelling salesman visits every VERTEX. Pick by what must be covered.
Read the notes
Full study notes for Route inspection & travelling salesman
Topic 3.16 hub
Route algorithms (HL only)
More from Topic 3.16
All flashcards in this topic
Math AI exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free