D1 3.1 - Route inspection
Find a shortest inspection route that travels along every edge and returns to its start. You will identify odd vertices, compare every possible pairing, specify the repeated edges, and adapt the parity reasoning when different start and finish vertices are prescribed.
Even and odd degree
A worker must inspect every road in a network. Is adding a short return journey enough, or can some roads be avoided on the way back? The surprising answer depends first on how many roads meet at each junction, rather than on their lengths.
The network below has edges , with total length . All weights in this lesson's pictured network are kilometres.
[DIAGRAM: asset_name: Four odd junctions; asset_slug: inspection-network; caption: A, B, D and E have odd degree; C has even degree.; description: Undirected network on A B C D E with edges AB 6 AC 7 BC 2 BD 3 CD 1 CE 8 DE 4 AE 5. Each vertex is labelled with its degree: A 3 B 3 C 4 D 3 E 3.]
At each intermediate visit on a closed route, an arrival uses one edge and a departure uses another. These traversals come in pairs. To traverse every edge exactly once and return to the start, every vertex must therefore have even degree. In a connected graph that condition is also sufficient: an Eulerian circuit uses every edge exactly once and returns to its start.
Odd vertices and inspection routes
An odd vertex has odd degree; an even vertex has even degree. A closed route inspection problem, also called the Chinese postman problem, asks for a minimum-length closed walk using every edge at least once. Repeating an edge means traversing it again, adding its weight again.
Here the degree sum is , twice the eight edges. Odd vertices always occur in an even number. With no odd vertices, no repetition is needed. With exactly two odd vertices, an open walk can use every edge once by starting at one and ending at the other. Closing that walk requires extra traversals.
Do not confuse this with a shortest path between two places or with visiting every vertex. Inspection requires every edge, including an expensive edge even if a cheaper connection exists.
Key idea
For a closed inspection route, duplicate connections until all degrees are even. For an open route, exactly the prescribed distinct start and finish must remain odd.
Test the distinction between an open and a closed route.
Pairing two or four odd vertices
Duplicating a path changes the parity of its two endpoints; each internal vertex gains two traversals and keeps its parity.
Thus odd vertices must be joined in pairs using shortest connecting routes. Their drawn separation does not matter. With two odd vertices there is one pairing. With four, say , there are exactly three:
Each expression uses shortest route lengths, which need not be direct edge weights. Compare the three totals before choosing.
Closed inspection length
For a connected undirected network with zero, two or four odd vertices,
With zero odd vertices, the additional total is zero. Not in the formula booklet: learn it.
Worked example 1: two odd vertices
Remove edge from the pictured network. Find the shortest closed inspection length.
Plan. Recount degrees, pair the remaining odd vertices, and add their shortest connecting distance to the new edge total.
Now degrees of are , so only are odd. Their shortest distance is , either direct or via . The total edge length is .
Answer. Repeat a shortest -to- connection; minimum length .
Check. Duplicating increases each odd degree by , making both even; no other degree changes.
Change only by restoring . Its two endpoints become odd, giving four odd vertices and three comparisons.
Worked example 2: four odd vertices
Find the minimum closed inspection length in the original pictured network.
Plan. Pair in all three possible ways.
| Pairing | Shortest connecting lengths | Extra length |
|---|---|---|
Here uses ; can use . Neither pair name assumes a direct edge.
Answer. Repeat and , giving .
Check. Each of the four odd vertices gains one traversal. The lower possible extra cost is the smallest of all three totals, so this is optimal, not merely feasible.
A shortest pairing can be non-unique. Record all three totals even when one looks obviously small.
Repeating shortest connecting routes
Choosing a pair identifies endpoints; you must still identify the actual edges to repeat between them.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account