A cost no tour can go below
A tour found by any method gives an upper bound: the cheapest tour costs that much or less. A lower bound works the other way. It is a number that every tour costs at least, so the cheapest tour cannot cost less.
To find one, take any tour of the five towns and look at a single town, say A. The tour arrives at A along one road and leaves along another, so it uses exactly two roads at A. Now delete A and those two roads. What is left of the tour is a path through B, C, D and E, and a path that reaches every one of them is a spanning tree of those four towns.
The five towns of the nearest-neighbor lesson. A, in gold, is the town to delete.
The tree of what is left
Delete A and every road at A. Six roads remain, joining B, C, D and E. The part of any tour away from A is a spanning tree of these four towns, so it costs at least as much as their minimum spanning tree.
Kruskal’s algorithm finds that tree. In order of weight the roads are CD 2, BC 4, BE 5, CE 6, BD 7 and DE 10. CD, BC and BE are kept, none of them closing a cycle, and three edges join four towns. The tree costs 2 + 4 + 5 = 11.
With A deleted, the minimum spanning tree of the other four towns is CD, BC and BE, in gold, with total 2 + 4 + 5 = 11.
Putting the deleted town back
The tour’s two roads at A cost at least as much as the two cheapest roads at A. Those cost 3, to B, and 6, to D; the other two cost 8 and 9.
So every tour costs at least 11 + 3 + 6 = 20, and no tour can cost under 20. That is the lower bound from deleting A.
The tree of 11 together with A’s two cheapest roads, AB and AD, in gold: 11 + 3 + 6 = 20.
The bound is usually not a tour
The five gold edges are not a tour. B meets three of them, AB, BC and BE, and E meets only one, so no round trip uses exactly these roads. The bound is a cost that every tour must reach, not a tour that costs it.
If the edges of the bound do happen to form a tour, that tour costs exactly the lower bound, so no tour is cheaper and it is the answer. The second application below ends that way.
Deleting each town in turn
Any town can be deleted, and each choice gives a lower bound. Deleting B: the roads among A, C, D and E in order are CD 2, then AD 6 and CE 6, which are equal, then AC 8, AE 9 and DE 10. CD, AD and CE are kept, in either order, since neither closes a cycle, so the tree costs 2 + 6 + 6 = 14. The two cheapest roads at B are AB 3 and BC 4, so the bound is 14 + 3 + 4 = 21.
Deleting C gives 14 + 2 + 4 = 20, deleting D gives 12 + 2 + 6 = 20, and deleting E gives 9 + 5 + 6 = 20. Every one of these is true, so the cheapest tour costs at least each of them, and the best lower bound is the largest: 21.
The nearest-neighbor tour from A gives the upper bound 28, so at first the cheapest tour lies between 20 and 28. The tour from B costs 22, and the bound from deleting B is 21, so the cheapest tour lies between 21 and 22. Costing all twelve tours confirms that the cheapest is 22.
Deleting B instead: the tree CD, AD and CE costs 2 + 6 + 6 = 14, and B’s two cheapest roads, AB and BC, add 3 + 4. The bound is 21.
The usual mistakes
Adding back only the cheapest road at the deleted town. A tour arrives at the town and leaves it again, so it uses two roads there, and the bound uses the two cheapest.
Including the deleted town in the spanning tree. The tree joins only the other four towns; the deleted town comes back through its two roads.
Taking the smaller of two lower bounds as the better one. Both are true, so every tour costs at least 21, and 21 says more than 20.
Expecting some tour to cost exactly the lower bound. Here the best lower bound is 21 and the cheapest tour is 22.
Weather stations and a courier
In the first application below, a technician’s round trip of six weather stations gets two lower bounds, from deleting two different stations. In the second, a courier’s proposed route turns out to cost exactly the lower bound, which proves that no route is shorter.
Worked example: A Technician Servicing Six Weather Stations, and the Least Length a Round Trip Could Have
Question A technician drives round six weather stations A, B, C, D, E and F in a national park, visiting each one once and returning to the station where she started. The table gives the shortest road distances in kilometers: A–B 27, A–C 16, A–D 18, A–E 21, A–F 15, B–C 37, B–D 11, B–E 34, B–F 28, C–D 30, C–E 12, C–F 13, D–E 29, D–F 22, E–F 9. (a) Find a lower bound for the length of her round trip by deleting station A. (b) Find the lower bound given by deleting station B. Which of the two is the better lower bound?
1.Delete A and every road at A. Kruskal's algorithm on B, C, D, E and F takes E–F (9), B–D (11) and C–E (12), rejects C–F (13) because C and F are already joined through E, and takes D–F (22). The tree is 9 + 11 + 12 + 22 = 54 km.
With A deleted, the minimum spanning tree of the other five is 54 km. Each edge is ringed once. 2.The two shortest roads at A are A–F (15) and A–C (16). (a) The lower bound is 54 + 15 + 16 = 85 km.
(a) Add the two shortest roads at A, 15 and 16: 54 + 15 + 16 = 85 km. 3.Delete B instead. On A, C, D, E and F the algorithm takes E–F (9) and C–E (12), rejects C–F (13), takes A–F (15), rejects A–C (16) because A and C are already joined through F and E, and takes A–D (18). The tree is 9 + 12 + 15 + 18 = 54 km.
With B deleted, the minimum spanning tree of the other five is also 54 km. 4.The two shortest roads at B are B–D (11) and A–B (27), so this lower bound is 54 + 11 + 27 = 92 km.
Add the two shortest roads at B, 11 and 27: 54 + 11 + 27 = 92 km. 5.(b) Deleting B gives 92 km. Every round trip is at least 85 km and at least 92 km, so the better lower bound is the higher one, 92 km.
(b) Every round trip is at least 92 km, the better lower bound.
Answer: (a) 85 km; (b) 92 km, which is the better lower bound
Common mistakes
- Adding only the shortest road at the deleted station. A round trip arrives at the station and leaves it again, so it uses two roads there.
- Taking the smaller value, 85 km, as the better lower bound. Both bounds are true, so every round trip is at least 92 km, and the higher bound says more.
More spanning trees and route problems problems, worked step by step →
Worked example: A Hospital Lab's Courier Collecting Samples From Five Clinics, and Whether a Driver's Proposed Route Is the Shortest
Question A courier leaves the hospital lab L, collects samples from five clinics A, B, C, D and E, and returns to L. The table gives the shortest road distances in kilometers: L–A 27, L–B 5, L–C 17, L–D 8, L–E 14, A–B 30, A–C 16, A–D 29, A–E 25, B–C 20, B–D 6, B–E 13, C–D 21, C–E 22, D–E 9. No two distances are equal. (a) Use the nearest-neighbor algorithm starting at L for an upper bound, and delete clinic A for a lower bound. Between which two values does the length of the shortest round trip lie? (b) A driver proposes the route L–C–A–E–D–B–L. Find its length, and decide whether any round trip is shorter.
1.Nearest neighbor from L: L to B (5 km), B to D (6), D to E (9), E to C (22, against A at 25), C to A (16), and back from A to L (27). This round trip is 5 + 6 + 9 + 22 + 16 + 27 = 85 km, an upper bound.
Nearest neighbor from L gives a round trip of 85 km, an upper bound. 2.Delete A. Kruskal's algorithm on L, B, C, D and E takes L–B (5) and B–D (6), rejects L–D (8), takes D–E (9), rejects B–E (13) and L–E (14), and takes L–C (17). The tree is 5 + 6 + 9 + 17 = 37 km.
With A deleted, the minimum spanning tree of L, B, C, D and E is 37 km. 3.The two shortest roads at A are A–C (16) and A–E (25), so the lower bound is 37 + 16 + 25 = 78 km. (a) The shortest round trip is at least 78 km and at most 85 km.
(a) The lower bound is 37 + 16 + 25 = 78 km, so the shortest trip is between 78 and 85 km. 4.The proposed route is L–C 17, C–A 16, A–E 25, E–D 9, D–B 6 and B–L 5, a total of 17 + 16 + 25 + 9 + 6 + 5 = 78 km.
The proposed route, each leg ringed in the row it leaves, is 78 km. 5.(b) The route is 78 km. No round trip can be shorter than the lower bound of 78 km, and this route equals it, so no round trip is shorter. Check: without A the route is the path C–L–B–D–E, which is the tree from the second step, and it uses the two shortest roads at A.
(b) It meets the lower bound, so no round trip is shorter.
Answer: (a) Between 78 km and 85 km; (b) 78 km, and no round trip is shorter
Common mistakes
- Doubting the proposed route because the nearest-neighbor trip is 85 km. The upper bound says only that the shortest trip is at most 85 km; a 78 km route is allowed, and meeting the lower bound makes it the shortest.
- Assuming that some route always reaches the lower bound. In general the shortest round trip can be longer than the bound; here a route is known to be the shortest only because its length equals the bound.
More spanning trees and route problems problems, worked step by step →