Travelling salesman: bounds and practical problems Problem set B One question at a time

The complete graph shows the distances between five points, A to E. Use the deleted vertex method.

1. (a) Delete vertex D. Find a lower bound for the travelling salesman problem.

   • Delete D. Kruskal on A, B, C, E: AB (5), AC (6), AE (7). Minimum spanning tree weight = 5 + 6 + 7 = 18.
   • The two shortest edges at D: DA (2) and DE (2).
   • LB = 18 + 2 + 2 = 22.

2. (b) Delete vertex B. Find a lower bound.

   • Delete B. Kruskal on A, C, D, E: AD (2), DE (2), AC (6). Minimum spanning tree weight = 2 + 2 + 6 = 10.
   • The two shortest edges at B: BD (4) and BA (5).
   • LB = 10 + 4 + 5 = 19.

3. (c) Which of your two lower bounds is the better one? Give a reason.

   • 22 (delete D) and 19 (delete B).
   • The better lower bound is the larger, so 22.

The graph shows the roads between five towns A to E, with distances in km. It is not complete.

1. (a) Construct the table of shortest distances. Write down each entry that is not simply the weight of a road, with the route that gives it.

   • AC: no direct road
   • AD: no direct road
   • CE: no direct road
   • All other entries equal the weight of the road.

2. (b) Use the nearest neighbour algorithm on the table, starting at E, to find an upper bound for the travelling salesman problem.

   • Nearest neighbour from E: EB (3), BA (10), AD (21), DC (6), CE (16).
   • Upper bound = 3 + 10 + 21 + 6 + 16 = 56.

3. (c) Write down the route in the original graph that has this length. Which towns are visited more than once?

   • AD is A-B-D
   • CE is C-B-E
   • Route in the original graph: E-B-A-B-D-C-B-E.
   • Length 56. Vertices visited more than once: B.

The table shows the shortest distances, in km, between six towns. Use the nearest neighbour algorithm, starting at C, to find an upper bound for the travelling salesman problem.

• Nearest neighbour from C: CA (13), AD (12), DF (6), FB (11), BE (12), EC (19).
• Upper bound = 13 + 12 + 6 + 11 + 12 + 19 = 73.

A technician must visit five offices, A to E, once each and return to the first office. The graph shows the driving times in minutes between the offices. A route A-C-B-E-D-A has length 16 minutes.

1. (a) Delete vertex D. Find a lower bound for the travelling salesman problem.

   • Delete D. Kruskal on A, B, C, E: BC (2), AC (4), BE (6). Minimum spanning tree weight = 2 + 4 + 6 = 12.
   • The two shortest edges at D: DA (2) and DE (2).
   • LB = 12 + 2 + 2 = 16.

2. (b) What does your lower bound tell you about the route A-C-B-E-D-A? Give a reason.

   • Lower bound 16; route length 16.
   • The shortest tour is at least the lower bound, and this route equals it.
   • So the route is a shortest tour.

A minibus starts from the school at A, visits five pick-up points, B to F, and returns to A. The graph shows the roads, with driving times in minutes. The minibus may use a road or a pick-up point more than once.

1. (a) Construct the table of shortest distances. Write down each entry that is not simply the weight of a road, with the route that gives it.

   • AC: no direct road
   • AD: no direct road
   • BC: the road is 12, but B-D-C is shorter
   • BF: no direct road
   • CE: no direct road
   • CF: no direct road
   • DE: the road is 13, but D-B-E is shorter
   • DF: no direct road
   • All other entries equal the weight of the road.

2. (b) Use the nearest neighbour algorithm on the table, starting at A, to find an upper bound.

   • Nearest neighbour from A: AE (10), EF (5), FB (12), BD (3), DC (4), CA (18).
   • Upper bound = 10 + 5 + 12 + 3 + 4 + 18 = 52.

3. (c) Write down the route on the original graph that has this length. Say which places are visited more than once.

   • FB is F-E-B
   • CA is C-D-B-A
   • Route in the original graph: A-E-F-E-B-D-C-D-B-A.
   • Length 52. Vertices visited more than once: B, D, E.

4. (d) Delete E from the table and find a lower bound. Write down the two values between which the shortest possible route must lie.

   • Delete E. Kruskal on A, B, C, D, F: BD (3), CD (4), BC (7) skipped, AB (11), BF (12). Minimum spanning tree weight = 3 + 4 + 11 + 12 = 30.
   • The two shortest edges at E: EF (5) and EB (7).
   • LB = 30 + 5 + 7 = 42.
   • 42 ≤ shortest route ≤ 52.

The table shows the shortest distances, in minutes, between six places. Find a lower bound and an upper bound for the travelling salesman problem.

1. (a) Delete C and find a lower bound.

   • Delete C. Kruskal on A, B, D, E, F: AE (5), AB (7), AF (10), BE (10) skipped, BF (11) skipped, EF (12) skipped, DE (13). Minimum spanning tree weight = 5 + 7 + 10 + 13 = 35.
   • The two shortest edges at C: CA (4) and CE (9).
   • LB = 35 + 4 + 9 = 48.

2. (b) Delete F and find a lower bound.

   • Delete F. Kruskal on A, B, C, D, E: AC (4), AE (5), AB (7), CE (9) skipped, BE (10) skipped, BC (11) skipped, DE (13). Minimum spanning tree weight = 4 + 5 + 7 + 13 = 29.
   • The two shortest edges at F: FA (10) and FC (10).
   • LB = 29 + 10 + 10 = 49.

3. (c) Use the nearest neighbour algorithm from E to find an upper bound. Write down the interval that the length of the shortest tour must lie in, using the better lower bound. Can you say the route is optimal?

   • Nearest neighbour from E: EA (5), AC (4), CF (10), FB (11), BD (19), DE (13).
   • Upper bound = 5 + 4 + 10 + 11 + 19 + 13 = 62.
   • Better lower bound: 49 (from deleting F). Shortest tour between 49 and 62.
   • 49 ≠ 62, so you cannot say the tour is optimal.