Route inspection

Why edges have to be repeated

Take the network to be connected: no closed route covers every edge of a disconnected network. A closed route using every edge exactly once then exists only when every node has even order, since each visit to a node uses two of its edges. Odd nodes therefore force repetition, and repeating an edge amounts to adding a duplicate, which raises the order of both its ends by one.

So the job is to pair up the odd nodes and repeat a shortest path between each pair. Shortest path, not shortest edge. The shortest path between two odd nodes may run through several edges and past other nodes, and repeating an edge between two even nodes would only make matters worse by turning them odd.

Calculating the minimum route length

For a connected network, the length of the shortest closed route is the total weight of all the edges plus the least pairing cost. Four odd nodes give three pairings; six give fifteen, which is as far as a question will go, and a network with more than six odd nodes comes with a restriction that cuts the list down.

Counting the pairings is a question in its own right. Take the first odd node: it can be paired with any of the others, and whichever it takes, the rest have to be paired among themselves in the same way. So with 2n odd nodes there are 2n − 1 choices for the first, then 2n − 3 for the next unpaired node, and so on down to 1, giving the product of the odd numbers 1 × 3 × 5 × ... × (2n − 1). Four odd nodes give 3 × 1 = 3, six give 5 × 3 × 1 = 15, and eight give 7 × 5 × 3 × 1 = 105, which is why the cap sits where it does.

Fifteen is few enough to list in full. Setting them out in five groups of three, one group for each partner of the first node, keeps the list complete. The example below works those fifteen through in numbers.

Describe the drawing

A grid of fifteen boxes in five rows of three. Each row fixes the node A is paired with, from B at a cost of 4 down to F at 6, and the three boxes in the row are the three ways the remaining four odd nodes can then be paired off. The number at the right of each box is the whole cost of that pairing, A's own pair included. The first box of the first row is filled amber: A with B, C with D and E with F, at 4 plus 3 plus 6, comes to 13, and no other pairing of the fifteen comes near it. Added to the network's total weight of 96 it gives a shortest closed route of 109.

Two variations come up. With no odd nodes, nothing is repeated and the answer is simply the total weight. If the route need not return to the start, leave two odd nodes unpaired to be the ends of the route, pair the rest as cheaply as possible, and start and finish at the two left over. With four odd nodes that means repeating one pair only, so choose the pair whose shortest path is least and leave the other two as the ends. The two left out need not be the pair with the longest shortest path between them: with AB 5, AD 9, AE 13, BD 7, BE 9 and DE 9, repeating AB at 5 is cheapest and leaves D and E as the ends, although AE at 13 is the longest of the six.

Limitations of the route-inspection model

The network is a model, and the 69 inherits whatever went into it. Four assumptions were made before any arithmetic started: each street became one edge, walking it either way cost the same, junctions became nodes, and the round had to finish where it began. A question asking you to evaluate the model is asking which of those four the situation supports, and the answer is usually that three do and one does not.

Modifying one of them is arithmetic rather than a new method, though it rarely stops at a single number. Close a road and two things move together: the total weight falls by that edge's weight, and the orders of its two ends each drop by one, so the list of odd nodes changes and the pairings have to be worked out again from scratch. Revise a weight and the total moves, and a shortest path between two odd nodes may reroute, which can hand the cheapest pairing to a different pair.

Refining means changing the graph itself. One-way streets need a digraph, and pairing odd nodes has nothing to say there, since what has to be matched is nodes with more arcs in than out against nodes with more out than in. A gritting lorry that treats a dual carriageway as two roads wants two edges where the map draws one. A round that may finish anywhere drops the closing condition, which is the variation above.

Then judge the answer rather than reporting it. The output is not the number 69 but the sentence it stands for: the shortest round covers every street and walks AB, DC and CE a second time, at a cost of 69 in whatever unit the weights carry. Put that way it can be tested against the situation by a reader who knows the streets, which a bare 69 cannot be.