Practice IB Mathematics Applications & Interpretation (AI) Topic AHL 3.16—tree and Cycle Algorithms, Chinese Postman, Travelling Salesman with authentic exam-style questions for both SL and HL students. This question bank focuses on the exact syllabus content for AHL 3.16—tree and Cycle Algorithms, Chinese Postman, Travelling Salesman and mirrors Paper 1, 2, 3 style where relevant.
Get instant solutions, detailed explanations, and build confidence with questions aligned to IB examiner expectations.
A utility worker must inspect all pipelines in a network, represented by the graph below, starting and ending at vertex X. Weights are in kilometers.
(a) Use Dijkstra's algorithm to find the shortest path from to (km). Show your working.
(b) the shortest path and its length (km).
A park ranger must patrol all trails in a national park, represented by the graph below, starting and ending at the ranger station (vertex S). Edge weights represent distances in kilometers.
(a) Verify whether the graph is planar. your answer.
(b) the minimum distance for the ranger's patrol using the Chinese Postman algorithm.
(c) If the ranger can start at S and end at A, find the minimum distance and specify the repeated edges.
A drone delivery company connects six mountain lodges, to , with flight times (in minutes) given in the table below. The graph is complete, and the table represents edge weights.
| — | 5 | 9 | 11 | 14 | 18 | |
| 5 | — | 4 | 8 | 12 | 15 | |
| 9 | 4 | — | 6 | 7 |
(b) Delete vertex . Find a lower bound for the travelling salesman problem, starting and returning to .
(c) Use the nearest neighbour algorithm, starting at , to find an upper bound for the travelling salesman problem.
A logistics company plans to visit six depots (). Travel times (hours) are given in the matrix below.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | - | 3 | 5 | 7 | 9 | 11 |
| B | 3 | - | 4 | 6 | 8 | 10 |
| C | 5 | 4 | - | 5 | 7 | 9 |
| D | 7 | 6 | 5 | - | 4 | 8 |
| E | 9 | 8 | 7 | 4 | - | 6 |
(a) Kruskal's algorithm to find the minimum spanning tree, listing edges in order of selection and stating the total weight.
(b) Find a lower bound for the travelling salesman problem using the deleted vertex method with vertex .
(c) Use the deleted vertex method with vertex to find an improved lower bound.
A logistics company connects six warehouses, A to F, with travel times (in hours) given in the table below. The graph is complete, and the table represents edge weights.
| — | 4 | 7 | 10 | 12 | 15 | |
| 4 | — | 5 | 8 | 11 | 14 | |
| 7 | 5 | — | 6 | 9 | 13 |
(b) Delete vertex A. Find a lower bound for the travelling salesman problem, starting and returning to A.
(c) Use the nearest neighbour algorithm, starting at A, to find an upper bound for the travelling salesman problem.
(a) Use Prim's algorithm, starting at vertex , to find the minimum spanning tree (MST) for the graph. the edges in the order in which they are added and the total weight of the MST.
(d) the lower bound obtained by deleting vertex , instead of vertex , and why this provides a better lower bound than the one found in Part 2.
(a) Use Prim's algorithm, starting at vertex A, to find the minimum spanning tree (MST) for the graph. the edges in the order in which they are added and the total weight of the MST.
(d) the lower bound obtained by deleting vertex F, instead of vertex A, and why this provides a better lower bound than the one found in part (b).
| 13 |
| 11 | 8 | 6 | — | 5 | 10 |
| 14 | 12 | 7 | 5 | — | 6 |
| 18 | 15 | 13 | 10 | 6 | — |
| 11 |
| 10 |
| 9 |
| 8 |
| 6 |
| - |
| 10 | 8 | 6 | — | 7 | 12 |
| 12 | 11 | 9 | 7 | — | 8 |
| 15 | 14 | 13 | 12 | 8 | — |
