Unit 3: Geometry and Trigonometry
Topic 3.16: Route algorithms (HL only) Questions
Practice 20 exam-style questions for IB Math AI SL Topic 3.16. Review the question stems below, then unlock the full Question Bank to access markschemes, model answers, and AI grading.
1Write down1 mark
2026
Write down whether an Eulerian trail exists, and where it must start.
Markscheme and model answer locked
Unlock Question21 mark
2026
If every vertex of a connected graph has even degree, the Chinese postman route length equals:
Markscheme and model answer locked
Unlock Question31 mark
2026
The nearest-neighbour algorithm for the TSP gives:
Markscheme and model answer locked
Unlock Question41 mark
2026
A spanning tree on 10 vertices has how many edges?
Markscheme and model answer locked
Unlock Question51 mark
2026
Dijkstra's algorithm is best described as finding:
Markscheme and model answer locked
Unlock Question6Write down1 mark
2026
Write down the number of edges in any spanning tree of the graph.
Markscheme and model answer locked
Unlock Question71 mark
2026
In Kruskal's algorithm, an edge is rejected when it:
Markscheme and model answer locked
Unlock Question8Find2 marks
2026
Kofi, a technician, visits five wind turbines, A, B, C, D and E, each once, starting and finishing at home, H. The distances between the locations, in km, are shown in the table.
With H deleted, the minimum spanning tree for A, B, C, D and E has weight 41 km. Hence find a lower bound for the shortest total distance.
| A | B | C | D | E | H | |
|---|---|---|---|---|---|---|
| A | – | 15 | 22 | 9 | 18 | 12 |
| B | 15 | – | 11 | 20 | 16 | 25 |
| C | 22 | 11 | – | 14 | 8 | 19 |
| D | 9 | 20 | 14 | – | 13 | 17 |
| E | 18 | 16 | 8 | 13 | – | 21 |
| H | 12 | 25 | 19 | 17 | 21 | – |
With H deleted, the minimum spanning tree for A, B, C, D and E has weight 41 km. Hence find a lower bound for the shortest total distance.
Markscheme and model answer locked
Unlock Question9Write down1 mark
2026
Seven fields, A to G, on a farm are to be joined by irrigation pipes. The cost, in hundreds of dollars, of each possible pipe is shown in the table. Every route not listed is impossible.
The minimum spanning tree consists of the edges AC, BC, EG, DE, CE, DF.
Write down the minimum cost of connecting the seven sites.
| Edge | Cost |
|---|---|
| AB | 8 |
| AC | 5 |
| BC | 6 |
| BD | 11 |
| CD | 12 |
| CE | 9 |
| DE | 7 |
| DF | 10 |
| EF | 13 |
| EG | 6 |
| FG | 14 |
The minimum spanning tree consists of the edges AC, BC, EG, DE, CE, DF.
Write down the minimum cost of connecting the seven sites.
Markscheme and model answer locked
Unlock Question10Find5 marks
2026
A site has eight buildings, A to H, to be joined by underground cables. The site map shows that a railway line runs between E and G. The graph S shows the cost, in dollars, of installing a cable along each possible connection.
Starting at B, use the nearest neighbour algorithm to find an upper bound for the installation cost of a network in the form of a Hamiltonian cycle. (Although the graph is not complete, a table of least distances is not needed here.)
| Edge | Cost (\$) |
|---|---|
| AB | 7 640 |
| AD | 10 630 |
| AE | 8 120 |
| BC | 9 350 |
| BD | 7 290 |
| CD | 8 870 |
| CE | 11 470 |
| CF | 11 890 |
| CH | 10 240 |
| DE | 9 780 |
| DF | 8 410 |
| EF | 11 067 |
| EG | 23 563 |
| FG | 7 938 |
| FH | 12 510 |
| GH | 9 160 |
Starting at B, use the nearest neighbour algorithm to find an upper bound for the installation cost of a network in the form of a Hamiltonian cycle. (Although the graph is not complete, a table of least distances is not needed here.)
Markscheme and model answer locked
Unlock Question11Find2 marks
2026
A technician must service six wind turbines, A to F, starting and finishing at A. The travelling times, in minutes, between the turbines are shown in the table.
The data can be represented by a weighted complete graph G. The minimum spanning tree of the subgraph of G obtained by deleting A has weight 144 minutes.
Hence find a lower bound for the travelling salesman problem of visiting every vertex and returning to the start.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | – | 42 | 57 | 66 | 71 | 38 |
| B | 42 | – | 35 | 49 | 80 | 52 |
| C | 57 | 35 | – | 29 | 61 | 73 |
| D | 66 | 49 | 29 | – | 44 | 58 |
| E | 71 | 80 | 61 | 44 | – | 36 |
| F | 38 | 52 | 73 | 58 | 36 | – |
The data can be represented by a weighted complete graph G. The minimum spanning tree of the subgraph of G obtained by deleting A has weight 144 minutes.
Hence find a lower bound for the travelling salesman problem of visiting every vertex and returning to the start.
Markscheme and model answer locked
Unlock Question12Write down1 mark
2026
Sam visits a science museum and wants to go on all five shows, starting and finishing at the entrance A. The shows are labelled: A = Entrance/Exit; B = Bubbles; C = Circuits; D = Dinosaurs; E = Electricity; F = Fossils. A graph shows the main paths; the weights are the walking times, in minutes, along each direct path, and the graph has exactly the edges listed.
Let be the shortest possible time, in minutes, to visit all the shows, beginning and ending at A. Sam finds upper bounds for of 43 minutes (a Hamiltonian cycle) and 49 minutes (nearest neighbour). Deleting A gives a lower bound of 33 minutes, and deleting each other vertex in turn gives the following lower bounds.
Sam writes the smallest interval for , based on these bounds, in the form .
Write down the value of .
| Edge | Time (minutes) |
|---|---|
| AB | 3 |
| AC | 7 |
| AD | 11 |
| AE | 10 |
| AF | 4 |
| BC | 5 |
| BD | 6 |
| CF | 10 |
| DE | 8 |
Let be the shortest possible time, in minutes, to visit all the shows, beginning and ending at A. Sam finds upper bounds for of 43 minutes (a Hamiltonian cycle) and 49 minutes (nearest neighbour). Deleting A gives a lower bound of 33 minutes, and deleting each other vertex in turn gives the following lower bounds.
| Deleted vertex | B | C | D | E | F |
|---|---|---|---|---|---|
| Lower bound | 36 | 33 | 36 | 36 | 33 |
Sam writes the smallest interval for , based on these bounds, in the form .
Write down the value of .
Markscheme and model answer locked
Unlock Question13Find6 marks
2026
Sara must inspect a network of irrigation channels, walking along each channel at least once. The times, in minutes, to inspect each channel are shown in the table (junctions are labelled with letters). If Sara walks along a channel a second time, that walk takes half the inspection time. The total of all the times is 74 minutes.
Sara begins and ends at A. A new channel is added joining F and G. It takes 12 minutes to inspect.
(i) Find which irrigation channels now need to be walked a second time for the inspection to take the minimum possible time. Justify your answer.
(ii) Write down the minimum possible time for the inspection.
| Irrigation channel | Time (minutes) |
|---|---|
| AB | 6 |
| BC | 5 |
| AC | 8 |
| CE | 7 |
| EF | 9 |
| CF | 4 |
| DE | 11 |
| EG | 6 |
| DG | 8 |
| AD | 10 |
Sara begins and ends at A. A new channel is added joining F and G. It takes 12 minutes to inspect.
(i) Find which irrigation channels now need to be walked a second time for the inspection to take the minimum possible time. Justify your answer.
(ii) Write down the minimum possible time for the inspection.
Markscheme and model answer locked
Unlock Question14Find3 marks
2026
For the network PQ = 3, PR = 7, QR = 2, QS = 6, RS = 4, use Prim's algorithm starting at P. List the edges in the order they are added and give the total weight.
Markscheme and model answer locked
Unlock Question15Find3 marks
2026
Kofi, a technician, visits five wind turbines, A, B, C, D and E, each once, starting and finishing at home, H. The distances between the locations, in km, are shown in the table.
Starting at H, use the nearest-neighbour algorithm to find an upper bound for the shortest total distance.
| A | B | C | D | E | H | |
|---|---|---|---|---|---|---|
| A | – | 15 | 22 | 9 | 18 | 12 |
| B | 15 | – | 11 | 20 | 16 | 25 |
| C | 22 | 11 | – | 14 | 8 | 19 |
| D | 9 | 20 | 14 | – | 13 | 17 |
| E | 18 | 16 | 8 | 13 | – | 21 |
| H | 12 | 25 | 19 | 17 | 21 | – |
Starting at H, use the nearest-neighbour algorithm to find an upper bound for the shortest total distance.
Markscheme and model answer locked
Unlock Question16Determine5 marks
2026
The table shows a network of roads in a village; the weights are the lengths of the roads in metres. The letters are junctions.
Sofia delivers leaflets to every house on every road, and the total distance travelled is to be as small as possible.
The route starts and finishes at junction A. Determine the minimum total distance.
| Road | Length (m) |
|---|---|
| AB | 40 |
| AC | 25 |
| BC | 30 |
| BD | 45 |
| CD | 20 |
| CE | 35 |
| DE | 15 |
| DF | 50 |
| EF | 28 |
| EG | 33 |
| FG | 22 |
| FH | 26 |
| GH | 31 |
| AH | 60 |
Sofia delivers leaflets to every house on every road, and the total distance travelled is to be as small as possible.
The route starts and finishes at junction A. Determine the minimum total distance.
Markscheme and model answer locked
Unlock Question17Find2 marks
2026
Rosa, a vet, visits five farms, A, B, C, D and E, each once, starting and finishing at home, H. The distances between the locations, in km, are shown in the table.
With H deleted, the minimum spanning tree for A, B, C, D and E has weight 130 km. Hence find a lower bound for the shortest total distance.
| A | B | C | D | E | H | |
|---|---|---|---|---|---|---|
| A | – | 42 | 65 | 38 | 57 | 24 |
| B | 42 | – | 31 | 70 | 49 | 45 |
| C | 65 | 31 | – | 46 | 28 | 53 |
| D | 38 | 70 | 46 | – | 33 | 41 |
| E | 57 | 49 | 28 | 33 | – | 62 |
| H | 24 | 45 | 53 | 41 | 62 | – |
With H deleted, the minimum spanning tree for A, B, C, D and E has weight 130 km. Hence find a lower bound for the shortest total distance.
Markscheme and model answer locked
Unlock Question181 mark
2026
Prim's algorithm differs from Kruskal's mainly because it:
Markscheme and model answer locked
Unlock Question19Use2 marks
2026
A water authority can lay pipes between 4 pumping stations P, Q, R, S. Lengths (km): PQ = 3, PR = 7, QR = 2, QS = 6, RS = 4. Use Kruskal's algorithm to find the minimum spanning tree and its total length.
Markscheme and model answer locked
Unlock Question20Find2 marks
2026
A site has eight buildings, A to H, to be joined by underground cables. The site map shows that a river runs between A and G. The graph S shows the cost, in dollars, of installing a cable along each possible connection.
The minimum spanning tree for S uses the edges AD, EF, BC, AB, DE, FH, DG.
Hence find the minimum installation cost for cables that connect all the buildings.
| Edge | Cost (\$) |
|---|---|
| AB | 9 120 |
| AC | 10 450 |
| AD | 8 730 |
| AG | 22 747 |
| BC | 8 940 |
| BE | 11 280 |
| CE | 9 660 |
| CF | 12 380 |
| DE | 9 310 |
| DG | 10 872 |
| DH | 13 400 |
| EF | 8 810 |
| EH | 12 950 |
| FH | 9 940 |
| GH | 11 620 |
The minimum spanning tree for S uses the edges AD, EF, BC, AB, DE, FH, DG.
Hence find the minimum installation cost for cables that connect all the buildings.
Markscheme and model answer locked
Unlock QuestionReady to practice Topic 3.16?
Get instant AI feedback on your answers, view detailed markschemes, and track your progress across all IB Math AI SL topics.