Every street, and back to the start
A postman must walk along every street of a neighborhood at least once, and finish where he started. The streets are the edges of a network, and their lengths are the weights. The problem is to find the shortest such route. It is also called the route inspection problem, and it is the same problem for a snowplow, a street sweeper or a road inspector.
Every street has to be walked, so the route is at least the total of all the streets. Here that is 5 + 3 + 4 + 6 + 2 = 20. The only question is how much has to be walked twice.
Four junctions and five streets, totaling 20. The small number beside each junction is its degree: 2, 3, 3 and 2.
Odd vertices force a repeat
If every vertex had even degree, an Eulerian circuit would walk every street exactly once and come home, and the answer would be 20.
Here B and C have degree 3. A closed route arrives at a vertex and leaves it again, using two street ends each time it passes, and its start and finish pair up in the same way. So a closed route uses the streets at each vertex an even number of times. B has three streets, so at least one street at B must be walked twice, and the same holds at C.
B and C, in gold, are the two vertices of odd degree.
The cheapest route between the odd vertices
Walking a route from B to C a second time adds 1 to the number of street ends used at B and at C, and 2 at each vertex in between, so every count becomes even. The extra distance is the length of that route, so take the shortest route from B to C.
There are three: the street BC, 4; B to D to C, 6 + 2 = 8; and B to A to C, 5 + 3 = 8. The direct street is the shortest, so BC is the street walked twice.
The street BC, in gold, costs 4. Both ways around, by D and by A, cost 8.
The route itself
Draw BC twice. Now A and D have degree 2 and B and C have degree 4: every degree is even, so an Eulerian circuit exists on the new network. One is A-B-C-B-D-C-A, which walks AB, BC, CB, BD, DC and CA.
Its length is 5 + 4 + 4 + 6 + 2 + 3 = 24, which is every street once, 20, plus the repeat, 4. No closed route over every street can be shorter.
BC drawn twice, in gold. Every degree is now even, 2, 4, 4 and 2, and the route A-B-C-B-D-C-A covers it in 24.
Four odd vertices
In the network below, every pair of the four vertices is joined, so all four have degree 3. The streets total 4 + 5 + 3 + 6 + 8 + 7 = 33. Four odd vertices must be joined in two pairs, and there are three ways to pair them. Each pairing costs the shortest route for each of its pairs.
A with B and C with D: 4 + 3 = 7. A with C and B with D: 8 + 7 = 15. A with D and B with C: 6 + 5 = 11. In each case the direct street is the shortest route; A to C, for instance, is 8 direct, against 4 + 5 = 9 through B and 6 + 3 = 9 through D.
The cheapest pairing is A with B and C with D, at 7, so AB and CD are walked twice. The shortest closed route is 33 + 7 = 40, for example A-B-A-C-B-D-C-D-A. With six odd vertices there are 15 pairings to cost, and with eight there are 105.
Four vertices of degree 3. The cheapest pairing repeats the gold streets AB and CD, at 4 + 3 = 7, so the shortest closed route is 33 + 7 = 40.
When the route need not return
Sometimes the route may start at one vertex and finish at another. An open route can start at one odd vertex and finish at another, and those two need no repeat between them, because an Eulerian trail runs from one odd vertex to the other.
In the lesson’s network, B and C are the only odd vertices, so a route from B to C walks every street exactly once: for example B-A-C-B-D-C, of length 5 + 3 + 4 + 6 + 2 = 20.
With four odd vertices, two of them become the ends and only the other two are joined by a repeated route. So find the shortest of the six routes between odd vertices, repeat it, and start and finish at the other two. In the network above, the six are AB 4, AC 8, AD 6, BC 5, BD 7 and CD 3. The shortest is CD, so repeat CD and start and finish at A and B: 33 + 3 = 36, for example A-B-C-A-D-C-D-B.
The usual mistakes
Repeating the more expensive route. B to D to C costs 8 against 4 for BC, so repeating it gives 28 instead of 24.
Answering 20. With two odd vertices, no closed route can use every street exactly once.
Repeating only the direct street between two odd vertices. The shortest route can pass through other vertices, and then every street on that route is walked twice.
Pairing each odd vertex with its nearest neighbor one pair at a time. The pairings must be compared by their totals: in the network above, pairing B with its nearest odd vertex A happens to be best, but in the first application below it is not.
Salt and storms
In the first application below, a salt truck must cover every street and return to its depot, with four odd junctions to pair. In the second, a park ranger walks every path after a storm, first from the main gate and back, then from any junction to any other.
Worked example: A Salt Truck That Must Spread Salt on Every Street of a Neighborhood and Return to Its Depot
Question A salt truck must drive along every street of a neighborhood at least once, starting and finishing at its depot at junction A. One pass salts the whole width of a street. The streets, with their lengths in meters, are A–B 320, B–C 280, A–D 250, B–E 400, C–F 260, D–E 300, E–F 420, B–D 460 and B–F 600. (a) Which streets must the truck drive twice on a shortest route? (b) How long is that shortest route?
1.Count the streets at each junction: A has 2, B has 5, C has 2, D has 3, E has 3 and F has 3. The odd junctions are B, D, E and F.
Four junctions have an odd number of streets: B, D, E and F. 2.Four odd junctions can be paired in three ways. The shortest routes are B–D 460 and E–F 420; B–E 400 and D–F 720 (by D–E–F); B–F 540 (by B–C–F, shorter than the street B–F at 600) and D–E 300.
The three ways to pair the odd junctions, each with its shortest routes. 3.The three pairings total 460 + 420 = 880, 400 + 720 = 1120 and 540 + 300 = 840 m. The least is 840 m, pairing B with F and D with E.
The least total is 840 m: B with F by B–C–F, and D with E. 4.(a) The truck drives B–C, C–F and D–E twice. With these repeats, every junction has an even number of passes, so a closed route over every street exists.
(a) B–C, C–F and D–E are driven twice, drawn as dashed second lines. 5.The streets total 320 + 280 + 250 + 400 + 260 + 300 + 420 + 460 + 600 = 3290 m. (b) The shortest route is 3290 + 840 = 4130 m.
(b) The streets total 3290 m, and the route is 3290 + 840 = 4130 m.
Answer: (a) B–C, C–F and D–E; (b) 4130 m
Common mistakes
- Repeating the street B–F (600 m) to pair B with F. The route B–C–F is only 540 m, so the streets driven twice are B–C and C–F.
- Pairing B with its nearest odd junction, E (400 m), and then having to pair D with F at 720 m, a total of 1120 m. The pairings must be compared by their totals, not one pair at a time.
More spanning trees and route problems problems, worked step by step →
Worked example: A Park Ranger Checking Every Path After a Storm, From the Main Gate or Between Any Two Junctions
Question After a storm, a park ranger must walk along every path of a park at least once to check for fallen trees. The paths, with their lengths in meters, are G–H 150, G–K 170, H–M 130, K–M 140, M–N 190, M–R 160, N–R 230, H–N 280 and K–R 260, where G is the main gate. (a) How long is the shortest route that starts and finishes at G? (b) Instead, a colleague can drop her off by cart at any junction and collect her at any other. Where should she start and finish, and how long is her shortest route then?
1.Count the paths at each junction: G 2, H 3, K 3, M 4, N 3, R 3. The odd junctions are H, K, N and R. The paths total 150 + 170 + 130 + 140 + 190 + 160 + 230 + 280 + 260 = 1710 m.
The gate G has two paths. H, K, N and R have an odd number. 2.Find the shortest route between each pair of odd junctions: H–K 270 (by H–M–K), N–R 230, H–N 280, K–R 260, H–R 290 (by H–M–R) and K–N 330 (by K–M–N).
The shortest route between each pair of odd junctions. 3.The three pairings total 270 + 230 = 500, 280 + 260 = 540 and 290 + 330 = 620 m. (a) The least is 500 m, repeating H–M, M–K and N–R, so the shortest closed route is 1710 + 500 = 2210 m.
(a) Pairing H with K and N with R adds 500 m: 1710 + 500 = 2210 m. 4.An open route starts and finishes at two odd junctions, and only the other two need a repeated route between them. The shortest of the six routes is N–R at 230 m, so she should leave H and K as the ends.
An open route ends at two odd junctions. Repeating the shortest of the six routes, N–R, leaves H and K as the ends. 5.(b) She should start at H and finish at K, or the other way round, and the route is 1710 + 230 = 1940 m.
(b) From H to K, or K to H: 1710 + 230 = 1940 m.
Answer: (a) 2210 m; (b) start at H and finish at K (or the reverse), 1940 m
Common mistakes
- Starting and finishing at N and R because they are joined by the shortest route. The shortest route is the one she walks twice, so N and R are the junctions to join, and H and K are the ends.
- Taking the pairing from (a) and dropping the wrong repeat. Keeping H–M–K and leaving out N–R gives 1710 + 270 = 1980 m; all six routes must be compared, and the shortest one is kept.
More spanning trees and route problems problems, worked step by step →