Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-11/problems/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.11

Name Date

The travelling salesman: nearest neighbour Problem set A

Write the tour as a list of vertices and add the weights. Remember to return to the start. No calculator is needed.

Difficulty: first skills applying them stretch

Skills

  1. The table shows the distances in km between five towns. Use the nearest neighbour algorithm from C. Write down the tour and its length.

    ABCDEA–717238B7–151416C1715–1120D231411–4E816204–

  2. The graph shows the distances in km between five towns. Use the nearest neighbour algorithm from A. Write down the tour and its length.

    619131581418111624ABCDE

  3. The graph shows the distances in km between five towns. A route is A–B–D–C–E–A.

    102417111516186148ABCDE
    1. (a) Show that the route is a Hamiltonian cycle and find its length.
    2. (b) What does the length tell you about the shortest route that visits every town and returns?

  4. The table shows the distances in km between six towns. Use the nearest neighbour algorithm from B. Write down the tour and its length.

    ABCDEFA–121751123B12–1331019C1713–161824D5316–620E1110186–21F2319242021–

  5. A courier must visit 7 towns, starting and finishing at the same town. Every pair of towns is joined by a road. A tour and its reverse count as one tour.

    1. (a) How many different tours are there?
    2. (b) A computer checks 10 000 tours every second. How long would it take to check every tour for 14 towns? Give your answer in hours to 3 significant figures.

In context

  1. A bakery van leaves the depot A, delivers to five shops B to F and returns to A. The table shows the distances in km. Use the nearest neighbour algorithm from A. Write down the route and its length, and state what the length tells you about the shortest possible route.

    ABCDEFA–152161920B15–221158C2122–231418D61123–137E1951413–12F20818712–

  2. A tour guide visits six villages A to F and returns to her start. The table shows the distances in km.

    ABCDEFA–122011518B12–17161915C2017–9227D11169–1310E5192213–6F18157106–
    1. (a) Use the nearest neighbour algorithm from A. State the tour and its length.
    2. (b) Use the nearest neighbour algorithm from E. State the tour and its length.
    3. (c) State the best upper bound for the shortest route.

  3. A delivery driver finds a route of 55 km that visits every stop and returns to the depot, using the nearest neighbour algorithm. Later she finds a route of 51 km.

    1. (a) State the best upper bound for the shortest route.
    2. (b) Can the shortest route be 53 km? Explain.
    3. (c) Can the shortest route be 45 km? Explain.

Stretch

  1. The graph shows the distances in km between five towns.

    9104382320242218ABCDE
    1. (a) Use the nearest neighbour algorithm from A. State the tour and its length.
    2. (b) Find a Hamiltonian cycle shorter than your answer to part (a).
    3. (c) Does the nearest neighbour algorithm always give the shortest route? Use your answers to explain.

  2. The table shows the distances in km between five towns A to E. A salesman may start at any town.

    ABCDEA–2224143B22–171320C2417–129D141312–4E32094–
    1. (a) Use the nearest neighbour algorithm from each town in turn. Write down the length of each tour.
    2. (b) State the best upper bound and the tour that gives it.

jmaths.xyz · AI HL · AHL 1.11 The travelling salesman: nearest neighbour