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

Name Date

The travelling salesman: nearest neighbour Problem set B

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

Each question matches the question with the same number in set A. Do the ones you got wrong there.

Difficulty: first skills applying them stretch

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–

  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

  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.
    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 C. Write down the tour and its length.

    ABCDEFA–91381724B9–1619412C1316–211523D81921–1118E1741511–3F241223183–

  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?
    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.

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–

  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.
    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 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.
    2. (b) Can the shortest route be 50 km? Explain.
    3. (c) Can the shortest route be 42 km? Explain.

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.
    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 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.
    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