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/b/

jmaths

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

The travelling salesman: nearest neighbour Problem set B One question at a time

Try each question on paper first. Open the working a line at a time, then say whether you had it.

Skills

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

    ABCDEA–1114177B11–61519C146–109D171510–3E71993–
    • From D: E 3, C 10, B 15, A 17. Nearest: E (3)
    • From E: A 7, C 9, B 19. Nearest: A (7)
    • From A: B 11, C 14. Nearest: B (11)
    • Return C to D (10).
    • 3 + 7 + 11 + 6 + 10 = 37

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

    323151158713421ABCDE
    • From E: C 4, B 7, A 11, D 21. Nearest: C (4)
    • From C: B 5, D 13, A 23. Nearest: B (5)
    • From B: A 3, D 8. Nearest: A (3)
    • Return D to E (21).
    • 4 + 5 + 3 + 15 + 21 = 48

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

    7391721518231612ABCDE

    1. (a) Show that the route is a Hamiltonian cycle and find its length.

      • Towns used: A, D, B, E, C, each once, then back to A.
      • 9 + 5 + 18 + 16 + 3 = 51

    2. (b) What does the length tell you about the shortest route that visits every town and returns?

      • 51 is an upper bound.
      • Shortest ≤ 51 km; it may be shorter.

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

    ABCDEFA–91381724B9–1619412C1316–211523D81921–1118E1741511–3F241223183–
    • From C: A 13, E 15, B 16, D 21, F 23. Nearest: A (13)
    • From A: D 8, B 9, E 17, F 24. Nearest: D (8)
    • From D: E 11, F 18, B 19. Nearest: E (11)
    • From E: F 3, B 4. Nearest: F (3)
    • Return B to C (16). 13 + 8 + 11 + 3 + 12 + 16 = 63

  5. A tour guide must visit 8 villages, starting and finishing at the same village. Every pair of villages is joined by a path. A tour and its reverse count as one tour.

    1. (a) How many different tours are there?

      • (8 − 1)! ÷ 2 = 5040 ÷ 2 = 2520.

    2. (b) A computer checks 20 000 tours every second. How long would it take to check every tour for 15 villages? Give your answer in days to 3 significant figures.

      • Tours: (15 − 1)! ÷ 2 = 43 589 145 600.
      • Seconds: 43 589 145 600 ÷ 20 000 = 2179457.28.
      • Days: 2179457.28 ÷ 86 400 = 25.2.

In context

  1. A technician leaves the office A, visits five clients 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–916172022B9–2114618C1621–41124D17144–107E2061110–15F221824715–
    • From A: B 9, C 16, D 17, E 20, F 22. Nearest: B (9)
    • From B: E 6, D 14, F 18, C 21. Nearest: E (6)
    • From E: D 10, C 11, F 15. Nearest: D (10)
    • From D: C 4, F 7. Nearest: C (4)
    • Return F to A (22). 9 + 6 + 10 + 4 + 24 + 22 = 75
    • Upper bound: shortest ≤ 75 km.

  2. A sales rep visits six offices A to F and returns to the start. The table shows the distances in km.

    ABCDEFA–22101465B22–2313320C1023–192111D141319–918E63219–7F52011187–

    1. (a) Use the nearest neighbour algorithm from A. State the tour and its length.

      • A–F–E–B–D–C–A: 5 + 7 + 3 + 13 + 19 + 10 = 57

    2. (b) Use the nearest neighbour algorithm from E. State the tour and its length.

      • E–B–D–A–F–C–E: 3 + 13 + 14 + 5 + 11 + 21 = 67

    3. (c) State the best upper bound for the shortest route.

      • The smaller of 57 and 67 is 57.
      • Shortest route ≤ 57 km.

  3. A ferry operator finds a tour of 53 km that visits every island and returns to port, using the nearest neighbour algorithm. Later he finds a tour of 48 km.

    1. (a) State the best upper bound for the shortest route.

      • Smaller of 53 and 48: 48.
      • Shortest ≤ 48 km.

    2. (b) Can the shortest route be 50 km? Explain.

      • 50 > 48, and a route of 48 km exists.
      • So the shortest route cannot be that long.

    3. (c) Can the shortest route be 42 km? Explain.

      • 42 < 48, so the upper bound does not rule it out.
      • An upper bound gives no information about how much shorter the shortest route is.

Stretch

  1. This graph gives the distances in km between five stations.

    231946161171789ABCDE

    1. (a) Use the nearest neighbour algorithm from A. State the tour and its length.

      • A–D–E–B–C–A: 4 + 9 + 7 + 16 + 19 = 55

    2. (b) Find a Hamiltonian cycle shorter than your answer to part (a).

      • Try A–D–B–C–E–A: 4 + 11 + 16 + 8 + 6 = 45.
      • 45 < 55.

    3. (c) Does the nearest neighbour algorithm always give the shortest route? Use your answers to explain.

      • A shorter cycle exists, so the nearest neighbour length 55 is only an upper bound.

  2. The table shows the distances in km between five depots A to E. A driver may start at any depot.

    ABCDEA–15232016B15–8139C238–107D201310–14E169714–

    1. (a) Use the nearest neighbour algorithm from each depot in turn. Write down the length of each tour.

      • A: A–B–C–E–D–A = 64
      • B: B–C–E–D–A–B = 64
      • C: C–E–B–D–A–C = 72
      • D: D–C–E–B–A–D = 61
      • E: E–C–B–D–A–E = 64

    2. (b) State the best upper bound and the tour that gives it.

      • Smallest is 61, from D.
      • Shortest route ≤ 61 km.

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