D1 3.1 - The route inspection algorithm
You will minimise a route that covers every arc, compare all relevant odd-node pairings, identify the actual repeated arcs, and adapt the calculation for specified endpoints or closed roads.
Why some arcs must be repeated
An inspector starts at , must cover every track, and may finish at or . Can closing track make the best inspection route shorter? We will see that it can: both the work to cover and the graph's odd nodes change.
You already know
In a connected undirected graph, all even nodes permit an Eulerian circuit; exactly two odd nodes permit an open Euler trail between them. Use shortest-path distances between nodes, which need not be direct arc weights.
Our network has weights
The four nodes have order ; has order . The total weight of all its arcs is .
[DIAGRAM: asset_name: A five-node inspection network; asset_slug: 9fm0-d1-169-inspection-network; caption: A, B, C and D are odd; X is even. Every original track must be covered.; description: An undirected five-node network with AX1, BX1, AC3, AD8, BC4, BD6, CD5; X subdivides the top A-to-B connection and the unmarked diagonal crossing is not a node.]
Route inspection problem
Find a shortest route traversing every arc of a connected undirected network at least once. In the closed problem, the route must return to its starting node. It is also called the Chinese postman problem.
A closed route needs even order at every node when repeated traversals are counted as extra copies of arcs. Duplicating a path changes parity at its two endpoints. Every intermediate node gains two incident arc ends, so its parity is unchanged.
For example, repeating the path changes from odd to even while adding two to 's already even order. Pairing odd endpoints tells us which paths to duplicate.
Key idea
The repeated traversals repair parity. Pair nodes using shortest paths, then state the actual arcs on those paths.
An arc and a path between its endpoints are different pieces of information.
The closed route inspection algorithm
First calculate the original total weight. Then find the cheapest extra paths that make every node even. With four odd nodes, there are exactly three complete pairings; compare their total costs, not individual pairs in isolation.
Closed route inspection algorithm
Identify the odd nodes. List every distinct way to pair them, and calculate each pairing's total using shortest-path distances. Duplicate the paths in a least-cost pairing. Add this extra cost to the total weight of all original arcs.
With no odd nodes, no repetition is needed. With two odd nodes, duplicate a shortest path between them. With four odd nodes, list all three pairings. Questions involving more than four odd nodes provide extra information restricting the pairings; use those restrictions.
Minimum closed inspection length
For original total arc weight and least total pairing cost ,
Not in the formula booklet: learn it.
Why does the best pairing give a route? The duplicated paths make every node even while preserving connectedness, so the augmented graph has an Eulerian circuit. The starting node can be anywhere on that circuit; it does not change the minimum closed length.
[DIAGRAM: asset_name: Extra copies make the network Eulerian; asset_slug: 9fm0-d1-169-duplicated-arcs; caption: Repeating AX, BX and CD adds 7 and makes every node even.; description: The original inspection network with separate blue parallel copies of AX, BX and CD, identifying actual repeated tracks rather than an imaginary AB arc.]
Worked example 1: all three pairings
Question. Find a minimum closed inspection length for the original network. State the arcs repeated.
Plan. Pair the odd nodes , using shortest-path distances, then add the smallest extra cost to .
The shortest pair distances are via , , , , , .
| Pairing | Extra cost |
|---|---|
Why use in the table? It is a shortest-path distance through , even though no direct track exists.
Answer. Repeat , of total extra weight . The minimum closed length is .
Check. The added path repairs ; the added repairs . Every node is now even.
Worked example 2 changes only , from weight to weight . Recalculate the original total as well as the pairing costs.
Worked example 2: a changed best pairing
Question. Find a minimum closed inspection length when , with every other weight unchanged.
Plan. Update , check the shortest pair distances and compare all three pairings again.
The new original total is . The shortest -to- distance is : alternatives through or are longer.
| Pairing | Extra cost |
|---|---|
Why not retain the original repeated arcs? Their extra cost is no longer least; changing one weight can change the pairing that wins.
Answer. Repeat . The minimum length is .
Check. Each of gains one incident arc end, making all four even.
A pairing lists endpoints; a final answer must identify the actual duplicated tracks. If a shortest path uses several arcs, list all of them. Compare complete pairings even when one individual pair looks particularly cheap.
Watch out
Wrong: choose the shortest odd-node pair and pair the remainder without comparison. Right: calculate all complete pairing totals, then explicitly state the repeated arcs and the original-plus-extra length.
Change the same weight once more, creating a tie.
An inspection route with different endpoints
For an open route from to , those two nodes must end odd and every other node must end even. Do not automatically make the whole graph Eulerian: that would force a return to the start.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account