DB3 - Route inspection

Odd vertices and repeated roads

What is the shortest closed walk covering every road in the network AB 2, BC 3, CD 2, DA 4, AC 5, BD 6 kilometres? The roads work both ways and the inspector may repeat roads. A crossing of drawn roads is not a junction unless a node is marked.

[DIAGRAM: asset_name: Four odd junctions in an inspection network; asset_slug: aqa7367-route-network; caption: Each of the four junctions has degree 3, and the total road length is 22 kilometres; description: A weighted undirected four-node network has square boundary AB 2 BC 3 CD 2 DA 4 and crossing diagonals AC 5 BD 6. Only the four corner nodes are junctions. A note says the diagonal crossing is not a junction. Nodes A B C D are labelled degree 3. The sum of all six road weights is 22 kilometres.]

At each intermediate visit to a junction, a walk uses one road to enter and another to leave. In a closed walk, this pairing also applies at the start. Therefore a connected undirected graph has a closed walk using each arc exactly once precisely when all vertex degrees are even. Such a walk is an Eulerian circuit. With exactly two odd vertices, an Eulerian trail can start at one and finish at the other.

The original graph has four odd vertices, so a closed walk must repeat something. Think of each repeated road as adding a parallel copy of its arc. Duplicating a path changes the parity of its two endpoints: they gain one incident arc each. Each internal vertex gains two, so its parity stays unchanged. We need to make every degree even as cheaply as possible.

The number of odd vertices is even, because the sum of all degrees is twice the number of arcs. This is why odd vertices can be paired. If the graph is disconnected, one continuous walk cannot inspect all its components without additional links.

Check parity without needing a picture.

Pairing odd vertices by shortest paths

For a closed inspection route, add the total weight of all original arcs to the least extra weight needed to pair the odd vertices. For each pair use a shortest path in the original network, not necessarily a direct arc. With four odd vertices A, B, C, D there are three pairings: AB with CD, AC with BD, or AD with BC. With six odd vertices there are 15 pairings: fix the first vertex's partner in five ways, then pair the remaining four in three ways. Compare every possible pairing, unless a valid argument eliminates some.

For a small network, find shortest paths by comparing possible simple paths. With nonnegative weights, including a cycle cannot improve a path, so only paths without repeated vertices need consideration. Record the actual paths as well as their lengths: those are the roads to duplicate.

Change only AB from 2 to 7. Pairing the same letters automatically would now give the wrong minimum.

A pairing may have several equally short realisations. Any shortest path for each selected pair is acceptable, including overlapping paths; count every duplicated arc with its multiplicity.

Use a complete shortest-path table in a new case.

Open routes and prescribed endpoints

An open inspection route starts at $s$ and ends at a different node $t$. The augmented graph must have exactly these two odd nodes. For every vertex, ask whether its original parity already matches that target. Duplicate paths pairing the vertices whose parity must change.

If $O$ is the set of original odd vertices, the set to pair is $O\mathbin{\triangle}\{s,t\}$: remove an endpoint already in $O$, and add an endpoint not in $O$. This notation means “in exactly one of the two sets”. It handles even endpoints too. The closed case $s=t$ instead requires all original odd vertices to change parity.