Practice AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman with authentic IB Mathematics Applications & Interpretation (AI) exam questions for both SL and HL students. This question bank mirrors Paper 1, 2, 3 structure, covering key topics like core principles, advanced applications, and practical problem-solving. Get instant solutions, detailed explanations, and build exam confidence with questions in the style of IB examiners.
Paper
Level
Question 1
HLPaper 1
A logistics manager must visit six warehouses ( P to U ) to inspect inventory, starting and returning to P . The travel times (in hours) are given in the table below.
| P | Q | R | S | T | U | |
|---|---|---|---|---|---|---|
| P | - | 5 | 8 | 10 | 12 | 15 |
| Q | 5 | - | 6 | 9 | 11 | 14 |
| R | 8 | 6 | - | 7 | 10 | 13 |
| S | 10 | 9 | 7 | - | 8 | 12 |
| T | 12 | 11 | 10 | 8 | - | 9 |
| U | 15 | 14 | 13 | 12 | 9 | - |
1.[4]
Use Kruskal's algorithm to find the minimum spanning tree, listing edges in order of selection.
2.[2]
Find a lower bound for the travelling salesman problem starting and returning to P.
3.[4]
Apply the nearest neighbour algorithm starting at P to find an upper bound.
4.[2]
Explain how deleting vertex Q could improve the lower bound.
Question 2
HLPaper 2
A city maintenance crew must inspect all roads in a network represented by the weighted graph , where vertices represent intersections and edges represent roads with weights indicating distances in kilometers.
1.[3]
Verify that graph satisfies the handshaking lemma.
2.[2]
Determine whether graph has an Eulerian trail, giving a reason for your answer.
3.[7]
Use the Chinese Postman algorithm to find the minimum distance the crew must travel to inspect all roads, starting and ending at vertex A. Clearly show all stages of the algorithm.
4.[3]
If the crew can start at vertex A and end at vertex F , find the minimum distance they need to travel, explaining which edges should be repeated.
Question 3
HLPaper 2
A communication network has vertices with the following adjacency matrix.
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 |
1.[3]
Compute the number of walks of length 3 from U to X .
2.[3]
Determine if the graph is connected and find its diameter.
Question 4
HLPaper 1
A logistics company plans to visit six depots ( ) in a region, with travel times in hours given in the table 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 |
| - |
1.[4]
Apply Kruskal's algorithm to find the minimum spanning tree, listing edges in order of selection.
2.[2]
Find a lower bound for the travelling salesman problem starting and returning to A.
3.[4]
Use the deleted vertex method with vertex C to find an improved lower bound.
Question 5
HLPaper 2
Consider a weighted graph with vertices and the following adjacency matrix representing edge weights.
| 0 | 3 | 5 | 2 | |
| 3 | 0 | 4 | 6 | |
| 5 | 4 | 0 | 3 | |
| 2 | 6 | 3 | 0 |
1.[4]
Use Kruskal's algorithm to find the minimum spanning tree of .
2.[3]
Verify if the graph has an Eulerian circuit or trail.
Question 6
HLPaper 1
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 | - |
1.[4]
Use Prim's algorithm, starting at A, to find the minimum spanning tree, listing edges in order.
2.[2]
Find a lower bound for the travelling salesman problem starting and returning to A.
3.[4]
Use the nearest neighbour algorithm starting at A to find an upper bound for the travelling salesman problem.
4.[2]
Explain how deleting vertex B could improve the lower bound.
Question 7
HLPaper 2
A delivery network connects five distribution centers, labeled V, W, X, Y, Z, with edges representing direct delivery routes. The adjacency matrix of the graph is given below.
| 0 | 2 | 1 | 0 | 1 | |
| 2 | 0 | 1 | 1 | 0 | |
| 1 | 1 | 0 | 2 | 1 | |
| 0 | 1 | 2 | 0 | 1 | |
| 1 | 0 | 1 | 1 | 0 |
1.[3]
Draw the graph .
2.[2]
Determine the degrees of each vertex.
3.[3]
Use the adjacency matrix to compute the number of walks of length 2 from V to X.
4.[3]
Adding edge YZ increases degrees: Y: 4, Z: 4, others unchanged.
Question 8
HLPaper 1
A courier service operates between five locations ( J to N ). The cost matrix (in dollars) for deliveries is given below.
| J | K | L | M | N | |
|---|---|---|---|---|---|
| J | - | 20 | 25 | 30 | 35 |
| K | 20 | - | 15 | 22 | 28 |
| L | 25 | 15 | - | 18 | 24 |
| M | 30 | 22 | 18 | - | 20 |
| N | 35 | 28 | 24 | 20 | - |
1.[2]
Explain the difference between Prim's and Kruskal's algorithms for finding a minimum spanning tree.
2.[4]
Use Prim's algorithm starting at J to find the minimum spanning tree, listing edges.
3.[4]
Find an upper bound for the travelling salesman problem using the nearest neighbour algorithm starting at J.
Question 9
HLPaper 2
A telecommunications company is planning to lay fiber-optic cables between seven data centers, labeled A to G, in a region. The distances (in kilometers) between the centers are represented in the weighted graph below.
1.[3]
Verify that the graph satisfies the handshaking lemma.
2.[6]
Use the Chinese Postman algorithm to determine the minimum distance to traverse all cables, starting and ending at A. Show all stages.
3.[6]
A new cable is added from F to G with a distance of kilometers. Find the range of such that the minimum distance to traverse all cables, starting and ending at A, remains unchanged.
Question 10
HLPaper 2
A maintenance team must service all roads in a town, represented by the graph below, starting and ending at vertex M. Weights are in kilometers.
1.[2]
Determine if the graph has an Eulerian circuit, justifying your answer.
2.[6]
Use the Chinese Postman algorithm to find the minimum distance to service all roads. Show all stages.
3.[4]
If a new road is added from P to Q with distance 4 km , find the new minimum distance to service all roads, starting and ending at M.