Travelling salesman: bounds and practical problems Problem set A

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

1. (a) Delete vertex A. Find a lower bound for the travelling salesman problem.
2. (b) Delete vertex E. Find a lower bound.
3. (c) Which of your two lower bounds is the better one? Give a reason.

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.
2. (b) Use the nearest neighbour algorithm on the table, starting at C, to find an upper bound for the travelling salesman problem.
3. (c) Write down the route in the original graph that has this length. Which towns are visited more than once?

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

A cycling club plans a ride that visits five villages, A to E, once each and returns to the start. The graph shows the distances in km between the villages. A route A-C-D-B-E-A has length 17 km.

1. (a) Delete vertex A. Find a lower bound for the travelling salesman problem.
2. (b) What does your lower bound tell you about the route A-C-D-B-E-A? Give a reason.

A courier based in town A must deliver parcels to five other towns, B to F, and return to A. The graph shows the roads, with distances in km. The courier may use a town or a road 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.
2. (b) Use the nearest neighbour algorithm on the table, starting at A, to find an upper bound.
3. (c) Write down the route on the original graph that has this length. Say which places are visited more than once.
4. (d) Delete B from the table and find a lower bound. Write down the two values between which the shortest possible route must lie.

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

1. (a) Delete A and find a lower bound.
2. (b) Delete D and find a lower bound.
3. (c) Use the nearest neighbour algorithm from B 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?