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.
Use Dijkstra's algorithm to find the shortest path from to (km). Show your working.
State the shortest path and its length (km).
If the worker can start at and end at , find the minimum distance (km) to inspect all pipelines, specifying repeated edges.
Verify whether the graph is planar. Justify your answer.
Determine the minimum distance for the ranger's patrol using the Chinese Postman algorithm.
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 | 13 | |
| 11 | 8 | 6 | — | 5 | 10 | |
| 14 | 12 | 7 | 5 | — | 6 | |
| 18 | 15 | 13 | 10 | 6 | — |
Use Prim's algorithm, starting at vertex , to find the minimum spanning tree (MST) for the graph. List the edges in the order in which they are added and state the total weight of the MST.
Delete vertex . Find a lower bound for the travelling salesman problem, starting and returning to .
Use the nearest neighbour algorithm, starting at , to find an upper bound for the travelling salesman problem.
Calculate the lower bound obtained by deleting vertex , instead of vertex , and explain why this provides a better lower bound than the one found in Part 2.
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 |
| F | 11 | 10 | 9 | 8 | 6 | - |
Apply Kruskal's algorithm to find the minimum spanning tree, listing edges in order of selection and stating the total weight.
Find a lower bound for the travelling salesman problem using the deleted vertex method with vertex .
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 | |
| 10 | 8 | 6 | — | 7 | 12 | |
| 12 | 11 | 9 | 7 | — | 8 | |
| 15 | 14 | 13 | 12 | 8 | — |
Use Prim's algorithm, starting at vertex A, to find the minimum spanning tree (MST) for the graph. List the edges in the order in which they are added and state the total weight of the MST.
Delete vertex A. Find a lower bound for the travelling salesman problem, starting and returning to A.
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the travelling salesman problem.
Calculate the lower bound obtained by deleting vertex F, instead of vertex A, and explain why this provides a better lower bound than the one found in Part 2.