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 Question
21 mark
2026
If every vertex of a connected graph has even degree, the Chinese postman route length equals:
Markscheme and model answer locked
Unlock Question
31 mark
2026
The nearest-neighbour algorithm for the TSP gives:
Markscheme and model answer locked
Unlock Question
41 mark
2026
A spanning tree on 10 vertices has how many edges?
Markscheme and model answer locked
Unlock Question
51 mark
2026
Dijkstra's algorithm is best described as finding:
Markscheme and model answer locked
Unlock Question
6Write down1 mark
2026
Write down the number of edges in any spanning tree of the graph.
Markscheme and model answer locked
Unlock Question
71 mark
2026
In Kruskal's algorithm, an edge is rejected when it:
Markscheme and model answer locked
Unlock Question
8Find2 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.

ABCDEH
A–152291812
B15–11201625
C2211–14819
D92014–1317
E1816813–21
H1225191721–

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 Question
9Write 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.

EdgeCost
AB8
AC5
BC6
BD11
CD12
CE9
DE7
DF10
EF13
EG6
FG14

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 Question
10Find5 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.

EdgeCost (\$)
AB7 640
AD10 630
AE8 120
BC9 350
BD7 290
CD8 870
CE11 470
CF11 890
CH10 240
DE9 780
DF8 410
EF11 067
EG23 563
FG7 938
FH12 510
GH9 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 Question
11Find2 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.

ABCDEF
A–4257667138
B42–35498052
C5735–296173
D664929–4458
E71806144–36
F3852735836–

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 Question
12Write 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.

EdgeTime (minutes)
AB3
AC7
AD11
AE10
AF4
BC5
BD6
CF10
DE8

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 vertexBCDEF
Lower bound3633363633

Sam writes the smallest interval for , based on these bounds, in the form .

Write down the value of .
Markscheme and model answer locked
Unlock Question
13Find6 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.

Irrigation channelTime (minutes)
AB6
BC5
AC8
CE7
EF9
CF4
DE11
EG6
DG8
AD10

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 Question
14Find3 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 Question
15Find3 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.

ABCDEH
A–152291812
B15–11201625
C2211–14819
D92014–1317
E1816813–21
H1225191721–

Starting at H, use the nearest-neighbour algorithm to find an upper bound for the shortest total distance.
Markscheme and model answer locked
Unlock Question
16Determine5 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.

RoadLength (m)
AB40
AC25
BC30
BD45
CD20
CE35
DE15
DF50
EF28
EG33
FG22
FH26
GH31
AH60

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 Question
17Find2 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.

ABCDEH
A–4265385724
B42–31704945
C6531–462853
D387046–3341
E57492833–62
H2445534162–

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 Question
181 mark
2026
Prim's algorithm differs from Kruskal's mainly because it:
Markscheme and model answer locked
Unlock Question
19Use2 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 Question
20Find2 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.

EdgeCost (\$)
AB9 120
AC10 450
AD8 730
AG22 747
BC8 940
BE11 280
CE9 660
CF12 380
DE9 310
DG10 872
DH13 400
EF8 810
EH12 950
FH9 940
GH11 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 Question

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