Menu
Sign up Sign in

AI HL · AHL 1

Graph Theory

0 of 43 skills done

0
AHL 1.12

Travelling salesman: bounds and practical problems

AHL 1.12

Travelling salesman: bounds and practical problems

Target: I can find a lower bound for the travelling salesman problem by the deleted vertex method. (+4 more)

By the end of this section

Key points

Deleted vertex lower bound

  • A lower bound (LB) is a length that the shortest tour cannot be less than.
  • Method: delete one vertex and its edges. Find the minimum spanning tree of what is left (Kruskal). Add the two shortest edges that were at the deleted vertex.
  • Why it works: a tour uses two edges at the deleted vertex, and the rest of the tour joins every other vertex, so it is at least as long as the minimum spanning tree.
  • Each deleted vertex gives a lower bound. You want the largest one: it is the best. Try more than one vertex.

Putting the bounds together

  • The nearest neighbour algorithm gives an upper bound (UB). The deleted vertex method gives a lower bound. The shortest tour lies between them: LB ≤ shortest tour ≤ UB.
  • If a tour has the same length as a lower bound, that tour is a shortest tour. In particular, if UB = LB, the answer is exact.
  • If the bounds are not equal, do not say the tour is optimal. Give the interval.

Practical problems: graphs that are not complete

  • A real map is not a complete graph, and the direct road is not always the shortest way. Build a table of shortest distances first. Check every pair, including pairs that have a direct road.
  • Work on the table as a complete graph: nearest neighbour or deleted vertex.
  • Then convert the tour back. Replace each table edge that is not a road by the route that gives its shortest distance. The length stays the same.
  • A vertex on one of those routes may be visited more than once. Name every vertex that appears more than once in the route (the start and the finish count as one).

Explore: the travelling salesman problem

Nearest neighbour gives an upper bound for the shortest tour. The deleted vertex method gives a lower bound. Run both and see the shortest tour squeezed between them.

Start at

Upper bounds found
Lower bounds found

  1. Run nearest neighbour from each vertex in turn. Do you always get the same length? Which length would you quote as the upper bound?
  2. Delete a different vertex each time. Which gives the best lower bound: the largest or the smallest? Why?
  3. Why does a tour have to use two edges at the deleted vertex? Why must the rest of the tour be at least as long as the minimum spanning tree?
  4. On Graph 4 find a lower bound and an upper bound that are equal. What does that tell you about the tour?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
Deleting one vertex

The complete graph shows the distances, in km, between five villages. Delete vertex A and find a lower bound for the travelling salesman problem.

11671210295122ABCDE
Working
  1. Delete the vertex

    Remaining vertices: B, C, D, E

    Remove A and the four edges at A.

  2. 10295122BCDE
    Minimum spanning tree of the rest

    Kruskal: BD (2), DE (2), CD (5). Weight = 9

    Add the shortest edge each time. Skip any edge that makes a cycle.

  3. Two shortest edges at the deleted vertex

    AC (6) and AD (7)

    Any tour must enter and leave A, so it uses two edges at A. These are the shortest two.

  4. Add

    LB = 9 + 6 + 7 = 22

    No tour can be shorter than this.

Video walkthrough coming
Comparing two lower bounds

For the same graph, delete vertex D instead. Find this lower bound and say which of the two lower bounds is better.

11671210295122ABCDE
Working
  1. 1161210912ABCE
    Minimum spanning tree of the rest

    Kruskal on A, B, C, E: AC (6), BE (9), BC (10). Weight = 25

    Now D is the vertex that is out.

  2. Two shortest edges

    DB (2) and DE (2)

    The two shortest edges at D.

  3. Lower bound

    LB = 25 + 2 + 2 = 29

  4. Compare

    Delete A: 22. Delete D: 29.

    The larger value is closer to the true shortest tour, so the bound 29 is the better one.

Video walkthrough coming
When the bounds meet

The complete graph shows the distances, in km, between five depots. A driver finds the tour A-B-D-C-E-A, of length 30 km. Delete vertex A to find a lower bound. What does this tell you about the tour?

21075118106912ABCDE
Working
  1. 118106912BCDE
    Minimum spanning tree

    Without A: CD (6), BD (8), CE (9). Weight = 23

  2. Add the two shortest edges

    LB = 23 + 2 + 5 = 30

    The edges at A are AB and AE.

  3. Compare with the tour

    Tour length 30 = lower bound 30

    The shortest tour cannot be below the lower bound, and this tour reaches it.

  4. Conclude

    The tour A-B-D-C-E-A is optimal: the shortest length is 30 km.

    If a tour has the same length as a lower bound, it is a shortest tour.

Video walkthrough coming
A table of shortest distances

The graph shows the roads between five towns. It is not complete. Construct the table of shortest distances between the towns. Give the shortest distance between C and E.

54141091211ABCDE
Working
  1. Direct roads

    Pairs that are joined: AB (5), BC (4), CD (14), DE (10), EA (9), AC (12), AD (11)

    These go into the table first. Then check each pair for a shorter way round.

  2. Pairs that need a route

    AC: A-B-C = 9 (the direct road is 12, longer); BD: B-A-D = 16 (no direct road); BE: B-A-E = 14 (no direct road); CE: C-B-A-E = 18 (no direct road)

    Try every route between the two towns. Take the shortest. A direct road that is longer than a detour is replaced.

  3. ABCDEA-59119B5-41614C94-1418D111614-10E9141810-
    The table

    Every other entry is the weight of its road.

    The table is a complete graph on the five towns.

Video walkthrough coming
Upper bound, then back to the map

Use the table of shortest distances for the five towns. Use the nearest neighbour algorithm, starting at B, to find an upper bound. Then write the route in the original graph, with its length, and say which towns are visited more than once.

ABCDEA-59119B5-41614C94-1418D111614-10E9141810-
Working
  1. Nearest unvisited vertex each time

    BC (4); CA (9); AE (9); ED (10); DB (16)

    From each vertex go to the nearest vertex not yet visited. Finish by returning to B.

  2. Add up

    UB = 4 + 9 + 9 + 10 + 16 = 48

    This is an upper bound: a real tour of this length exists.

  3. 54141091211ABCDE
    Replace table edges by roads

    CA is C-B-A; DB is D-A-B

    A table edge that is not a road stands for the route that gives its shortest distance.

  4. The route and the repeats

    Route in the original graph: B-C-B-A-E-D-A-B. Length 48. Vertices visited more than once: A, B.

    The length does not change. A town on the way is visited more than once.

Video walkthrough coming