Travelling salesman: bounds and practical problems Problem set B

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.
2. (b) Delete vertex B. 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 E, 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 C, to find an upper bound for the travelling salesman problem.

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.
2. (b) What does your lower bound tell you about the route A-C-B-E-D-A? Give a reason.

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.
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 E 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 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.
2. (b) Delete F and find a lower bound.
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?