Edexcel International A Level Maths · D1 · Decision Mathematics 1
Route inspection and the travelling salesperson
28 free, high-quality past-paper-style questions on Route inspection and the travelling salesperson for Edexcel IAL Maths, each with a full mark scheme. For when you have finished the past papers, or want to practise one topic at a time.IAL Maths notes and flashcards →Not sure of your level? Diagnostic test →Multiple choice or structured questions, with the mark scheme as a separate PDF.28 new this month · 248 marks · Updated 26 October 2026 · Created by Evan Kotronis with AI assistance · How questions are checked
1IALM-D1-3-B-01D1 · ASEasy6 marks
A nature reserve has nine trails joining six points P, Q, R, S, T and U. The trails and the times, in minutes, to walk them are: PQ 8, PR 6, QR 12, QS 7, QT 10, RT 19, ST 18, SU 19, TU 16. The total time to walk all nine trails once is 115 minutes. A ranger must walk along every trail at least once, starting and finishing at the visitor centre at P.
Figure: trails in the reserve, times in minutes; not to scale
(a)
By considering the degrees of the vertices, explain why the ranger cannot walk each trail exactly once.
(2)
(b)
Find the minimum time for the ranger's walk, stating which trails are walked twice.
(3)
(c)
State the number of times the ranger passes through Q on this walk.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
degrees P 2, Q 4, R 3, S 3, T 4, U 2
B1
R and S have odd degree, so the network is not Eulerian and some trails must be repeated
B1
Part (b)
considers routes from R to S, e.g. RQS = 19, RPQS = 21, RTS = 37
M1
repeat RQ and QS
A1
115 + 19 = 134 minutes
A1
Part (c)
Q has degree 4 + 2 = 6, so 3 times ft from the repeated trails
B1
Exam tip: The repeated path between the two odd vertices is the shortest path, which need not be a single arc: R to S directly does not even exist here.
A machine paints the lines on a sports hall floor. The lines form a network with vertices A, B, C, D, E and F and arcs AB 8, BC 6, CD 7, DE 9, EF 5, FA 9, BD 10, DF 11 and BF 12 (lengths in metres). The machine must travel along every line, starting and finishing at A.
Figure: the lines before AD is added, lengths in metres; not to scale
(a)
Explain why the machine can paint every line exactly once and return to A, and find the length of its route.
(2)
(b)
A new line AD of length 21 m is added. Find the length of the shortest route that paints every line, including AD, and returns to A.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
degrees A 2, B 4, C 2, D 4, E 2, F 4: all even, so the network is Eulerian
B1
route length = total weight = 77 m
B1
Part (b)
A and D are now odd (degrees 3 and 5)
M1
shortest A to D: ABD = 18 (AFD = 20, AD = 21)
M1
77 + 21 + 18 = 116 m
A1
Common error: Forgetting to add the new line itself. The route must still cover AD once, then repeat the shortest path between the two new odd vertices.
A florist delivers to five shops, A, B, C, D and E, visiting each once and returning to the first. The table shows the least distances, in km, between the shops.
A
B
C
D
E
A
—
32
11
25
21
B
32
—
29
37
13
C
11
29
—
33
19
D
25
37
33
—
26
E
21
13
19
26
—
(a)
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the optimal route. Show your route clearly.
(3)
(b)
Repeat the nearest neighbour algorithm, starting at C.
(2)
(c)
State which of your answers is the better upper bound, giving a reason.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
A → C (11) → E (19) … nearest unvisited each time
M1
A C E B D A
A1
11 + 19 + 13 + 37 + 25 = 105 km
A1
Part (b)
C A E B D C
M1
11 + 21 + 13 + 37 + 33 = 115 km
A1
Part (c)
105 km, because it is the smaller (a route of this length exists, so the optimum is at most 105) ft
B1
Exam tip: At each step, read the row of the current shop and ignore every shop already visited. Only return to the start when every shop has been visited.
A bridge inspector must visit six bridges F, G, H, J, K and L, starting and finishing at F and visiting each bridge once. The table shows the least travel times, in minutes, between the bridges.
F
G
H
J
K
L
F
—
22
24
47
29
52
G
22
—
35
50
14
44
H
24
35
—
25
49
34
J
47
50
25
—
60
11
K
29
14
49
60
—
57
L
52
44
34
11
57
—
(a)
By deleting F, use Kruskal's algorithm to find a minimum spanning tree for the remaining five bridges. List the arcs in the order you consider them and state the weight of the tree.
(3)
(b)
Hence find a lower bound for the time of the inspector's tour.
(2)
(c)
The tour F H J L G K F takes 147 minutes. Use this and your answer to (b) to write down an interval for the time of the optimal tour.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
JL 11, GK 14, HJ 25 accepted
M1
HL 34 rejected (cycle), GH 35 accepted
A1
weight = 85
A1
Part (b)
two least arcs from F: FG 22 and FH 24
M1
85 + 22 + 24 = 131 minutes
A1
Part (c)
131 ≤ T ≤ 147 (minutes) ft
B1
Exam tip: Add the two least arcs from the deleted vertex to the residual tree, not the two arcs of the tree that touch it: in the residual tree it has no arcs at all.
Figure 1 shows the footpaths in a botanical garden. The number on each arc is the time, in minutes, to walk along that path. The total time to walk all ten paths once is 87 minutes. A gardener must walk along every path at least once, starting and finishing at the gate at A.
(a)
Use the degrees of the vertices to explain why the gardener must walk along some paths more than once.
(2)
(b)
Find the minimum time for the gardener's walk, stating which paths are walked twice.
(3)
(c)
State the number of times the gardener passes through C on this walk.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
degrees A 2, B 3, C 4, D 4, E 3, F 2, G 2: B and E are odd
B1
a closed route using every arc exactly once needs every vertex to be even, so some paths must be repeated
B1
Part (b)
considers paths from B to E, e.g. BCE = 16, BDE = 17
M1
repeat BC and CE
A1
87 + 16 = 103 minutes
A1
Part (c)
C has degree 4 + 2 = 6, so 3 times ft from the repeated paths
B1
Exam tip: The two odd vertices are not joined directly here, so compare every short way between them: two arcs via C (16) beats two arcs via D (17).
Figure 1 shows the seven streets of a small housing estate. The number on each street is its length in hundreds of metres, and the total length of the streets is 39 (3.9 km). A postal worker must walk along every street at least once, starting and finishing at the sorting office at P.
(a)
Write down the odd vertices of the network, and explain why the postal worker must repeat at least one street.
(2)
(b)
Find the length of the shortest route, stating which streets are walked twice.
(3)
(c)
State the number of times the postal worker passes through U.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
Q and T (degree 3)
B1
a closed route covering each street exactly once needs every vertex even, so some streets are repeated
B1
Part (b)
shortest Q to T: QRUT = 10, shorter than QT = 11 and QPST = 18
M1
repeat QR, RU and UT
A1
39 + 10 = 49 (4.9 km)
A1
Part (c)
U has degree 2 + 2 = 4, so 2 times ft
B1
Common error: Repeating the direct street QT because it joins the two odd vertices. The shortest path between them goes round through R and U.
A tour guide leads a walk that visits five landmarks A, B, C, D and E, each once, and returns to the landmark where it started. Figure 1 shows the least walking times, in minutes, between each pair of landmarks.
(a)
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the walk. Show your route clearly.
(3)
(b)
Use the nearest neighbour algorithm, starting at D, to find a second upper bound.
(2)
(c)
State which of your answers is the better upper bound, giving a reason.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
A → E (11) → B (17) … nearest unvisited each time
M1
A E B C D A
A1
11 + 17 + 12 + 16 + 19 = 75 minutes
A1
Part (b)
D C B A E D
M1
16 + 12 + 14 + 11 + 20 = 73 minutes
A1
Part (c)
73 minutes, the smaller value: a walk of that length exists, so the optimum is at most 73 ft
B1
Exam tip: From each landmark, read only the arcs to landmarks not yet visited. The last arc, back to the start, is forced: it is not a choice.
Figure 1 shows the cycle paths in a country park, with their lengths in km. The total length of the nine paths is 67 km. A cyclist wants to ride along every path, starting at the car park at C.
(a)
Explain why the cyclist can ride along every path exactly once, provided that she does not need to return to C, and state where her ride must finish.
(2)
(b)
State the length of this ride.
(1)
(c)
The cyclist decides instead to return to C at the end of her ride. Find the length of the shortest ride and state which paths are repeated.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
C and D have odd degree (3); A, B, E and F are even
B1
exactly two odd vertices, so a route using every arc once exists from C, finishing at D
B1
Part (b)
67 km (no path repeated)
B1
Part (c)
shortest D to C: DEC = 11 (DBC = 12)
M1
repeat DE and EC
A1
67 + 11 = 78 km
A1
Exam tip: A network with exactly two odd vertices can be traversed without repeats only from one odd vertex to the other. Returning to the start costs the shortest path between them.
An engineer must inspect every pipe in a water network. The network has junctions A to H and pipes AB 12, AC 13, AD 7, BC 7, BE 5, CD 15, CF 18, DF 7, DG 17, EF 20, EH 6, FG 8 and GH 8 (lengths in hundreds of metres), with total length 143. The engineer starts and finishes at C.
Figure: the pipe network, lengths in hundreds of metres; not to scale
(a)
Write down the odd vertices.
(1)
(b)
Use the route inspection algorithm to find the three possible pairings of the odd vertices and the total length of the repeated pipes for each.
(4)
(c)
State which pipes are inspected twice and find the length of the engineer's route.
(2)
(d)
State the number of times the engineer passes through junction H.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
A, B, E, G
B1
Part (b)
a correct pairing with shortest paths attempted
M1
AB + EG = 12 + 14 (EHG) = 26
A1
AE + BG = 17 (ABE) + 19 (BEHG) = 36
A1
AG + BE = 22 (ADFG) + 5 = 27
A1
Part (c)
repeat AB, EH and HG
A1
143 + 26 = 169 (16.9 km)
A1
Part (d)
H has degree 2 + 2 = 4, so 2 times ft
B1
Exam tip: The two pairings totalling 26 and 27 are very close: write all three totals so the comparison is visible, and name the repeated pipes, not just the extra length.
A snowplough must clear every road in a village. The road network has junctions P, Q, R, S, T, U, V and W and roads PQ 17, PS 21, QR 12, QT 22, RU 24, ST 26, SV 28, TU 22, TW 6, UW 26 and VW 17 (lengths in hundreds of metres), with total length 221. The odd vertices are Q, S, U and W.
Figure: the village roads, lengths in hundreds of metres; not to scale
(a)
The snowplough starts and finishes at its depot at P. Find the length of the shortest route, showing all your working.
(4)
(b)
The depot moves, and the snowplough now starts at Q but may finish at any junction. Determine where it should finish, and find the length of the shortest route.
Exam tip: With a fixed start at an odd vertex, try each of the other odd vertices as the finish and repeat the shortest path between the two that are left.
A district nurse visits five villages R, S, T, U and V. The roads between them are RS 27, RT 7, RV 20, ST 23, SU 6, TV 24 and UV 11 (lengths in km); there are no other roads. The nurse wants a table of least distances between the villages; part of it is shown.
R
S
T
U
V
R
—
27
7
20
S
27
—
23
6
T
7
23
—
24
U
6
—
11
V
20
24
11
—
Figure: roads between the villages, lengths in km; not to scale
(a)
Complete the table by finding the least distances RU, SV and TU, stating the route for each.
(3)
(b)
Starting at U, use the nearest neighbour algorithm on the completed table to find an upper bound for the length of the nurse's tour.
(3)
(c)
Interpret the tour in (b) as a route the nurse would actually drive on the road network.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
RU = 31 (R–V–U)
B1
SV = 17 (S–U–V)
B1
TU = 29 (T–S–U)
B1
Part (b)
U → S (6) → V (17) …
M1
U S V R T U
A1
6 + 17 + 20 + 7 + 29 = 79 km
A1
Part (c)
S → V is via U and T → U is via S
M1
U S U V R T S U
A1
Exam tip: Steps of a tour that use a table entry with no direct road must be replaced by the actual path, so villages can appear more than once in the practical route.
A band plans a tour of six cities T, U, V, W, X and Y, starting and finishing at T and playing in each city once. The table shows the least driving distances, in tens of km, between the cities.
T
U
V
W
X
Y
T
—
70
45
27
54
38
U
70
—
57
56
34
46
V
45
57
—
43
32
12
W
27
56
43
—
42
36
X
54
34
32
42
—
22
Y
38
46
12
36
22
—
(a)
Use Prim's algorithm, starting at T, to find a minimum spanning tree. List the arcs in the order in which they are selected and state the weight of the tree.
(3)
(b)
Hence find an initial upper bound for the length of the band's tour.
(1)
(c)
Use shortcuts to reduce this upper bound to a value below 215. State your tour and its length.
(3)
(d)
Explain why twice the weight of a minimum spanning tree is always an upper bound for the length of the optimal tour.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
TW (27), WY (36)
M1
YV (12), YX (22), XU (34) in this order
A1
weight = 131
A1
Part (b)
2 × 131 = 262 ft
B1
Part (c)
walks round the tree from T and replaces repeated sections by direct arcs
M1
tour T W Y V X U T
A1
27 + 36 + 12 + 32 + 34 + 70 = 211
A1
Part (d)
walking round the tree and back uses each tree arc twice and visits every city, so a closed route of that length exists (and the optimal tour, in which shortcuts replace any revisits, is no longer)
B1
Exam tip: When the walk round the tree has a choice of branch, try the cheaper order: here visiting V before X gives 211, while X before V gives 221.
A seaplane serves six islands A, B, C, D, E and F. A pilot must visit each island once and return to the starting island. The table shows the least flight times, in minutes, between the islands.
A
B
C
D
E
F
A
—
42
71
53
25
58
B
42
—
33
63
31
69
C
71
33
—
79
56
78
D
53
63
79
—
38
11
E
25
31
56
38
—
40
F
58
69
78
11
40
—
(a)
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the total flight time.
(3)
(b)
Use the nearest neighbour algorithm, starting at D, to find another upper bound.
(2)
(c)
By deleting A and finding a minimum spanning tree for the remaining islands, find a lower bound for the total flight time.
(2)
(d)
Deleting D instead gives a residual minimum spanning tree of weight 129. Find the corresponding lower bound.
(1)
(e)
Using your answers, write down the smallest interval for the optimal flight time.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
A → E (25) → B (31) …
M1
A E B C F D A
A1
25 + 31 + 33 + 78 + 11 + 53 = 231
A1
Part (b)
D F E A B C D
M1
11 + 40 + 25 + 42 + 33 + 79 = 230
A1
Part (c)
residual tree DF 11, BE 31, BC 33, DE 38: weight 113
M1
113 + 25 + 42 = 180
A1
Part (d)
129 + 11 + 38 = 178
B1
Part (e)
180 ≤ T ≤ 230 (minutes) ft
B1
Common error: Taking the smaller lower bound or the larger upper bound. The best interval uses the largest lower bound (180) and the smallest upper bound (230).
A canal company inspects every towpath in its network. The towpaths join locks K, L, M, N, P, Q and R and are KL 9, KM 12, LM 18, LN 4, MP 12, NP 15, NQ 14, PQ 14, PR 11 and QR 5 (lengths in km), total 114 km. Each inspection starts and finishes at K.
Figure: the towpaths, lengths in km; not to scale
(a)
Use the route inspection algorithm to find the length of the shortest inspection route, stating the towpaths that are inspected twice.
(5)
(b)
The towpath MP is permanently closed and will no longer be inspected. Find the length of the new shortest inspection route.
Figure 1 shows the pipelines between seven pumping stations A to G, with their lengths in km. The total length of the pipelines is 89 km. An engineer must inspect every pipeline, starting and finishing at station A.
(a)
Write down the odd vertices of the network.
(1)
(b)
Use the route inspection algorithm to find the three possible pairings of the odd vertices and the total length of the repeated pipelines for each.
(4)
(c)
State which pipelines are inspected twice and find the length of the engineer's route.
(2)
(d)
Write down a possible route for the engineer, starting and finishing at A.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
B, C, E and F
B1
Part (b)
a correct pairing with shortest paths attempted
M1
BC + EF = 12 (BGC) + 12 = 24
A1
BE + CF = 12 (BGE) + 14 (CGF) = 26
A1
BF + CE = 16 (BGF) + 10 (CGE) = 26
A1
Part (c)
BG, GC and EF
A1
89 + 24 = 113 km
A1
Part (d)
a closed route of 13 arcs using BG, GC and EF twice and every other pipeline once
M1
e.g. A B C D E F E G B G C G F A (any valid order)
A1
Exam tip: The direct pipeline BC (13) is longer than the path B–G–C (12). Always use the shortest path between each pair, not simply the arc that joins them.
Figure 1 shows the roads on a business park, with their lengths in hundreds of metres. The total length of the roads is 90. A road sweeper must sweep every road, starting from its depot at H.
(a)
Write down the odd vertices of the network.
(1)
(b)
The sweeper must return to H at the end. Find the length of the shortest route, stating the roads that are swept twice.
(4)
(c)
Instead, the sweeper must finish at the garage at T. Explain why the vertices that now need to be paired are H, Q, R and S, and find the length of the shortest route from H to T.
the route starts at H and ends at T, so H and T need odd degree and every other vertex even: H (even) needs one extra arc end, T (already odd) needs none
Exam tip: For a route with a fixed start and finish, list the vertices whose degree has the wrong parity: odd vertices that are not an end, plus any end that is even. Pair those.
A delivery driver must call at six shops A, B, C, D, E and F, starting and finishing at A. Figure 1 shows the only direct roads between the shops, with their lengths in km. Part of the table of least distances between the shops is shown below.
A
B
C
D
E
F
A
—
5
9
17
B
5
—
6
12
13
C
9
6
—
11
7
19
D
17
12
11
—
4
8
E
13
7
4
—
12
F
19
8
12
—
(a)
The driver applies the nearest neighbour method to the direct roads in Figure 1, starting at A. Show that this does not give a tour, and explain why a table of least distances is used instead.
(2)
(b)
Find the least distances AE, AF and BF, stating the route for each.
(3)
(c)
Use the nearest neighbour algorithm on the completed table, starting at A, to find an upper bound for the length of the driver's route.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
A → B (5) → C (6) → E (7) → D (4) → F (8)
M1
F is joined only to D and E, both visited, and there is no road F to A, so the tour cannot be completed; least distances give a complete network in which every step is possible
B1
Part (b)
AE = 16 (A–C–E)
B1
AF = 25 (A–B–D–F)
B1
BF = 20 (B–D–F)
B1
Part (c)
A → B (5) → C (6) → E (7) → D (4) → F (8) → A
M1
A B C E D F A
A1
5 + 6 + 7 + 4 + 8 + 25 = 55 km
A1
Exam tip: The last step back to the start uses the least distance from the table, here F to A = 25 km through D and B, even though there is no direct road.
A sales representative must visit six towns J, K, L, M, N and P, visiting each once and returning to the starting town. The table shows the least distances, in km, between the towns.
J
K
L
M
N
P
J
—
26
24
50
48
22
K
26
—
20
32
44
36
L
24
20
—
28
25
20
M
50
32
28
—
27
46
N
48
44
25
27
—
32
P
22
36
20
46
32
—
Figure 1 shows a minimum spanning tree for the six towns.
(a)
Find the weight of the minimum spanning tree in Figure 1, and hence write down an initial upper bound for the length of the tour.
(2)
(b)
Starting at J, use shortcuts to reduce the upper bound to a value below 160 km. State your tour and its length.
(3)
(c)
By deleting K, find a lower bound for the length of the tour.
(3)
(d)
Write down an interval within which the length of the optimal tour must lie.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
20 + 20 + 22 + 25 + 27 = 114
B1
2 × 114 = 228 km
B1
Part (b)
walks round the tree from J and replaces repeated sections by direct arcs from the table
Exam tip: When the walk round the tree branches at a junction such as L, try both orders of the branches: J P L K N M J gives 183, while J P L N M K J gives 152.
Figure 1 shows the paths in a nature reserve, with their lengths in hundreds of metres. The total length of the paths is 95. The path KL leads to a bird hide at L and is a dead end. A warden must walk along every path at least once.
(a)
Explain why, in any route that starts and finishes at the same point, the path KL is walked at least twice.
(2)
(b)
The warden starts and finishes at A. Use the route inspection algorithm to find the length of the shortest route, stating the paths that are walked twice.
(4)
(c)
A second warden starts at the hide at L and may finish anywhere. Find where this warden should finish and the length of the shortest route.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
L has degree 1
B1
a route that reaches L can only leave along KL again (and a route that starts at L must come back along KL), so KL is used twice
B1
Part (b)
odd vertices B, E, K, L; a pairing with shortest paths attempted
M1
BE + KL = 16 (BDE) + 5 = 21
A1
BK + EL = 18 (BDK) + 16 (EKL) = 34; BL + EK = 23 (BDKL) + 11 = 34
A1
repeat BD, DE and KL: 95 + 21 = 116 (11.6 km)
A1
Part (c)
L is the start, so the finish is one of B, E, K and the other two are joined: finish B, repeat EK = 11; finish E, repeat BK = 18; finish K, repeat BE = 16
M1
finish at B
A1
95 + 11 = 106 (10.6 km)
A1
Exam tip: A vertex of degree 1 is always odd. Starting the route there is the only way to avoid walking its single arc twice.
A helicopter must visit five remote weather stations P, Q, R, S and T, landing at each once and returning to its starting station. Figure 1 shows the least flying times, in minutes, between each pair of stations.
(a)
By deleting P, use Kruskal's algorithm to find a lower bound for the total flying time. List the arcs of the residual tree in the order you select them.
(3)
(b)
By deleting R, find a second lower bound.
(3)
(c)
State which of your lower bounds is better, giving a reason.
(1)
(d)
Show that the arcs used to obtain the lower bound in part (b) form a tour, and hence state the length of the optimal tour.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
QR 18, ST 20, RT 24
M1
weight 62
A1
62 + 22 + 27 = 111 minutes
A1
Part (b)
residual tree ST 20, PT 27, QS 29
M1
weight 76
A1
76 + 18 + 22 = 116 minutes
A1
Part (c)
116, because it is the larger: every tour is at least this long
B1
Part (d)
RQ, QS, ST, TP and PR form the cycle R Q S T P R, visiting every station once
M1
a tour equal to a lower bound must be optimal: 116 minutes
A1
Exam tip: A residual tree plus the two arcs from the deleted vertex is usually not a tour. When it is one, the lower bound is achieved and that tour is optimal.
A cleaning robot must travel along every corridor of a hospital wing. The corridors join points B, C, D, E, F, G, H and J and are BC 37, BD 47, CD 27, CE 59, DE 49, DG 12, EH 13, FG 58, FJ 27, GH 16, GJ 38 and HJ 33 (lengths in metres). The total length of the corridors is 416 m.
Figure: the corridors, lengths in metres; not to scale
(a)
Explain why the robot cannot travel along every corridor exactly once and return to its starting point.
(1)
(b)
The robot starts and finishes at its charging point B. Use the route inspection algorithm to find the length of the shortest route, stating the corridors that are travelled twice.
(5)
(c)
A second robot may start and finish at any points. Find the length of its shortest route and state where it should start and finish.
(3)
(d)
A new corridor of length x m is to be built between C and J, and it must also be cleaned. Find the range of values of x for which the shortest closed route, starting and finishing at B, would be shorter than your answer to (b).
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
C, E, H and J have odd degree (3), so the network is not Eulerian
B1
Part (b)
considers the three pairings of C, E, H, J
M1
CE + HJ = 59 + 33 = 92
A1
CH + EJ = 55 (CDGH) + 46 (EHJ) = 101 and CJ + EH = 77 (CDGJ) + 13 = 90
A1
repeat CD, DG, GJ and EH
A1
416 + 90 = 506 m
A1
Part (c)
repeats only the shortest path between two odd vertices
M1
EH = 13 is the least of 59, 55, 77, 13, 46, 33
A1
416 + 13 = 429 m, starting at C and finishing at J (or the reverse)
A1
Part (d)
C and J become even; only E and H are odd, so repeat EH = 13
M1
new length = 416 + x + 13 = 429 + x
A1
429 + x < 506 ⟹ 0 < x < 77
A1
Exam tip: The pairing using the two direct arcs CE and HJ (92) looks natural but is not the least: CJ + EH (90) wins because EH is so short. Always total all three.
A security officer must visit six checkpoints A, B, C, D, E and F on a business park each night, starting and finishing at A. The paths between checkpoints are AB 25, AC 28, BC 6, BD 21, BE 14, CE 19, DE 16, DF 11 and EF 15 (lengths in tens of metres); there are no other paths. Part of the table of least distances is shown.
A
B
C
D
E
F
A
—
25
28
39
B
25
—
6
21
14
29
C
28
6
—
19
D
21
—
16
11
E
39
14
19
16
—
15
F
29
11
15
—
Figure: paths between the checkpoints, lengths in tens of metres; not to scale
(a)
Complete the table by finding the least distances AD, AF, CD and CF.
(4)
(b)
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the officer's route.
(3)
(c)
Interpret your answer to (b) as the route the officer would actually walk.
(2)
(d)
By deleting A, find a lower bound for the length of the officer's route.
(3)
(e)
Hence write down an interval within which the length of the optimal route must lie.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
AD = 46 (A–B–D)
B1
AF = 54 (A–B–E–F)
B1
CD = 27 (C–B–D)
B1
CF = 34 (C–E–F)
B1
Part (b)
A → B (25) → C (6) → E (19) …
M1
A B C E F D A
A1
25 + 6 + 19 + 15 + 11 + 46 = 122 (1220 m)
A1
Part (c)
D to A is not a direct path: it goes D–B–A
M1
A B C E F D B A
A1
Part (d)
residual minimum spanning tree BC 6, DF 11, BE 14, EF 15
M1
weight 46
A1
46 + 25 + 28 = 99 (990 m)
A1
Part (e)
99 ≤ L ≤ 122 (tens of metres) ft
B1
Exam tip: A completed table of least distances must satisfy the triangle inequality: no entry can be larger than going via a third checkpoint. Use this to check your four new entries.
A maintenance boat services six wind turbines K, L, M, N, P and Q, visiting each once and returning to its start. Turbine Q is far offshore. The table shows the least sailing times, in minutes, between the turbines.
K
L
M
N
P
Q
K
—
30
31
24
34
74
L
30
—
56
17
61
62
M
31
56
—
47
8
69
N
24
17
47
—
53
79
P
34
61
8
53
—
68
Q
74
62
69
79
68
—
(a)
Use the nearest neighbour algorithm, starting at K, to find an upper bound for the total sailing time.
(3)
(b)
Use the nearest neighbour algorithm, starting at L, to find a second upper bound.
(2)
(c)
By deleting K, find a lower bound for the total sailing time.
(3)
(d)
By deleting Q, find a second lower bound.
(2)
(e)
What can you conclude about the boat's optimal tour? Give a reason.
A small town has five junctions V, W, X, Y and Z joined by the streets VW 11, VX 15, WX 6, WY 14, XY 3, XZ 8 and YZ 4 (lengths in hundreds of metres), total 61. A street sweeper must sweep every street, and a parcel van must call at every junction.
Figure: the streets, lengths in hundreds of metres; not to scale
(a)
The sweeper starts and finishes at its depot at V. Find the length of its shortest route.
(3)
(b)
A second sweeper may start and finish at any junctions. State where it should start and finish and the length of its route.
(2)
(c)
The van starts and finishes at V. Find the least distances VY and VZ, and then use the nearest neighbour algorithm on the table of least distances, starting at V, to find an upper bound for the length of the van's tour.
(3)
(d)
Write down the route the van actually drives for the tour in (c).
(1)
(e)
By deleting V, find a lower bound for the length of the van's tour, and hence give an interval for the optimal tour.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
odd vertices W and Y
B1
shortest W to Y is WXY = 9 (not WY = 14)
M1
61 + 9 = 70 (7 km)
A1
Part (b)
start at W and finish at Y (or the reverse)
B1
no streets repeated: 61 (6.1 km)
B1
Part (c)
VY = 18 (V–X–Y) and VZ = 22 (V–X–Y–Z)
B1
V W X Y Z V
M1
11 + 6 + 3 + 4 + 22 = 46
A1
Part (d)
V W X Y Z Y X V
B1
Part (e)
residual tree on W, X, Y, Z: XY 3, YZ 4, WX 6, weight 13
M1
13 + 11 + 15 = 39
A1
39 ≤ L ≤ 46
A1
Exam tip: Route inspection covers every arc; the travelling salesperson visits every vertex. Read which one the question wants before choosing a method.
Figure 1 shows the footpaths in a town park, with their lengths in tens of metres. The total length of the twelve existing footpaths is 106. The two dashed arcs are proposed new paths and are not part of the network in parts (a) and (b). A litter collector must walk along every existing footpath at least once.
(a)
The collector starts and finishes at A. Use the route inspection algorithm to find the length of the shortest route, stating the footpaths that are walked twice.
(5)
(b)
A second collector may start and finish at any points. Find the length of the shortest route and state where it should start and finish.
(3)
(c)
The park will build one of the proposed paths, either CG of length 10 or EG of length 14. The new path must also be walked. Determine which path gives the shorter route that starts and finishes at A, and find its length.
repeat only the shortest path between two odd vertices: CD = 6 is the least of 6, 16, 13, 22, 12, 19
M1
start at E and finish at G (or the reverse)
A1
106 + 6 = 112 (1120 m)
A1
Part (c)
with CG: C and G become even, D and E remain odd
M1
repeat DE = 22 (DCFE): 106 + 10 + 22 = 138
A1
with EG: E and G become even, repeat CD = 6: 106 + 14 + 6 = 126
A1
build EG: route 126 (1260 m), even though EG is the longer path
A1
Exam tip: A new arc between two odd vertices makes both even. What matters is the shortest path between the two odd vertices left over, not the length of the new arc alone.
A mobile library must visit six villages P, Q, R, S, T and U, starting and finishing at P. Figure 1 shows the roads between the villages, with their lengths in km. Part of the table of least distances between the villages is shown below.
P
Q
R
S
T
U
P
—
14
11
19
Q
14
—
9
17
17
R
11
9
—
15
8
27
S
17
15
—
10
12
T
19
17
8
10
—
20
U
27
12
20
—
(a)
Complete the table by finding the least distances PS, PU and QU.
(3)
(b)
Use Prim's algorithm on the completed table, starting at P, to find a minimum spanning tree. List the arcs in the order in which you select them, and state the weight of the tree.
(3)
(c)
Write down an initial upper bound for the length of the route. Use shortcuts to reduce it to a value below 90 km, stating your tour.
(3)
(d)
By deleting S, find a lower bound for the length of the route.
(3)
(e)
Write down an interval for the length of the optimal route, and state the route that the library actually drives for your tour in part (c).
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
PS = 26 (P–R–S)
B1
PU = 38 (P–R–S–U)
B1
QU = 29 (Q–S–U), less than the direct road of 31
B1
Part (b)
PR 11, RT 8
M1
RQ 9, TS 10, SU 12 in this order
A1
weight 50
A1
Part (c)
2 × 50 = 100 km ft
B1
walks round the tree from P, using shortcuts U to Q and Q to P
M1
P R T S U Q P: 11 + 8 + 10 + 12 + 29 + 14 = 84 km
A1
Part (d)
residual minimum spanning tree RT 8, QR 9, PR 11, TU 20
M1
weight 48
A1
48 + 10 + 12 = 70 km
A1
Part (e)
70 ≤ L ≤ 84 (km) ft
B1
P R T S U S Q P (U to Q is driven via S)
B1
Common error: Copying the direct road QU = 31 into the table. A table of least distances needs the shortest route, and Q–S–U is only 29 km.
Figure 1 shows the cables in a tunnel system that an inspection robot must travel along. The length of cable AB is x metres, where x > 0, and the other lengths, in metres, are shown on the figure. The robot must travel along every cable at least once, starting and finishing at E.
(a)
Write down, in terms of x, the total length of the cables, and list the odd vertices.
(2)
(b)
Given that x = 9, find the length of the robot's shortest route, stating which cables are repeated.
(4)
(c)
Find the range of values of x for which the cable AB is repeated in the robot's shortest route.
(3)
(d)
On one inspection the robot's shortest route was 91 m long and it repeated cable AB. Find x.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
x + 70
B1
A, B, C and D
B1
Part (b)
AB + CD = 9 + 15 (CFD) = 24
M1
AC + BD = 12 + 11 = 23; AD + BC = 20 (ABD) + 21 (BAC) = 41
A1
repeat AC and BD
A1
79 + 23 = 102 m
A1
Part (c)
AB is repeated only in the pairing AB + CD (AD + BC exceeds 23 whenever it uses AB); for x < 15 this costs x + 15
M1
x + 15 < 23
M1
0 < x < 8
A1
Part (d)
(x + 70) + x + 15 = 91
M1
x = 3, which lies in the range 0 < x < 8
A1
Exam tip: With an unknown length, write each pairing total as an expression, then compare them with inequalities. Check that the shortest paths you used stay shortest over the range you find.
A courier must visit five depots A, B, C, D and E, visiting each once and returning to the starting depot. Figure 1 shows the least travel times, in minutes, between each pair of depots. The least travel time between C and E is k minutes, where k ≠ 24.
(a)
By considering the times between B, C and E, explain why k ≥ 9.
(2)
(b)
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the tour in terms of k.
(3)
(c)
By deleting A, find a lower bound for the length of the tour, in terms of k, when 9 ≤ k < 24, and its value when k > 24.
(4)
(d)
Given that k = 30, find the lower bound obtained by deleting E, and hence give the smallest interval for the length of the optimal tour that your answers allow.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
the times are least times, so BE ≤ BC + CE (travelling via C cannot be quicker than the least time)
M1
26 ≤ 17 + k, so k ≥ 9
A1
Part (b)
A → B (18) → D (14) → C (19, less than DE = 24)
M1
A B D C E A
A1
18 + 14 + 19 + k + 30 = 81 + k
A1
Part (c)
residual tree contains BD 14 and BC 17
M1
E joins by CE = k if k < 24, otherwise by DE = 24
M1
two least arcs from A: 18 + 21 = 39
B1
lower bound 70 + k for 9 ≤ k < 24; 94 for k > 24
A1
Part (d)
residual tree BD 14, BC 17, AB 18: weight 49
M1
49 + 24 + 26 = 99
A1
99 ≤ T ≤ 111 (minutes)
A1
Exam tip: When an arc length is unknown, ask whether it changes any choice. Here CE is never compared at the nearest neighbour steps, so k only adds to the final total.
We use essential cookies to make this site work. With your permission we'd also use analytics and advertising cookies to understand which resources help students most and how families find us. Nothing optional is set unless you accept. Privacy policy
EssentialNeeded for the site and your cookie choice to work.
Always on
AnalyticsAnonymous visit statistics that help improve the free resources.
MarketingMeasures whether ads reach the right families. Off unless you turn it on.