The deleted-vertex method, best lower bound, the interval containing the optimal tour.
12 original questions, 78 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.
A travelling salesman problem has seven vertices, A to G. Vertex D and all of its arcs are deleted, and a minimum spanning tree for the remaining six vertices has weight 74
The arcs from D have weights 23, 18, 31, 40, 27 and 35
Find a lower bound for the length of the optimal tour.
2 marks
Show answer
115
2
The table shows the least distances, in km, between five bus garages, A to E, in Bristol.
A
B
C
D
E
A
−
29
13
48
18
B
29
−
20
70
47
C
13
20
−
56
31
D
48
70
56
−
55
E
18
47
31
55
−
By deleting E and all of its arcs, find a lower bound for the length of a tour of the five garages. Complete the table below.
3 marks
Show answer
130 km
3
The deleted vertex method is used to find lower bounds for a travelling salesman problem.
Explain why the method gives a lower bound for the length of the optimal tour.
Deleting different vertices gives lower bounds of 147, 152 and 139. The nearest neighbour algorithm from two vertices gives upper bounds of 186 and 179
Write down the smallest interval that must contain the length, L, of the optimal tour, giving reasons for your choice of each end.
4 marks
Show answer
a) Removing the deleted vertex from any tour leaves a path through all the other vertices, which is a spanning tree of them, so it is at least the RMST weight; the two tour arcs at the deleted vertex are at least the two least arcs from it.b) 152 ≤ L ≤ 179: the best lower bound is the largest, the best upper bound is the smallest.
4
The table below shows the least distances, in miles, between six market towns, A to F, in Norfolk.
By deleting A and all of its arcs, use Prim's algorithm, starting at B, to find a minimum spanning tree for the remaining five towns. State the order in which you select the arcs and the weight of the tree.
Hence find a lower bound for the length of a tour of all six towns.
5 marks
Show answer
a) BD, DC, CF, DE; weight 101 milesb) 183 miles
5
The table shows the least distances, in km, between six offices, A to F, of a firm in Glasgow.
A
B
C
D
E
F
A
−
19
58
45
51
31
B
19
−
39
40
32
18
C
58
39
−
42
60
36
D
45
40
42
−
71
22
E
51
32
60
71
−
50
F
31
18
36
22
50
−
By deleting A, find a lower bound for the length of a tour of the six offices.
By deleting E, find a second lower bound.
State the better lower bound, giving a reason.
6 marks
Show answer
a) 158 kmb) 177 kmc) 177 km, the larger
6
The table shows the least times, in minutes, for a minibus to travel between six schools, A to F, in Swansea.
A
B
C
D
E
F
A
−
19
30
41
11
46
B
19
−
49
35
25
29
C
30
49
−
65
37
72
D
41
35
65
−
31
51
E
11
25
37
31
−
48
F
46
29
72
51
48
−
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour of the schools.
By deleting F, find a lower bound for the length of the tour.
Hence write down an interval within which the length, T minutes, of the optimal tour must lie.
6 marks
Show answer
a) A - E - B - F - D - C - A, 211 minutesb) 166 minutesc) 166 ≤ T ≤ 211
7
The table below shows the least distances, in km, between six lighthouses, A to F, on the coast of Cornwall. An engineer must inspect every lighthouse and return to her start.
By deleting F, and using Prim's algorithm starting at A, find a lower bound for the length of her tour.
Show that the arcs you used in (a) form a tour, and state this tour.
Explain what you can deduce about this tour.
7 marks
Show answer
a) 201 kmb) F - A - C - D - E - B - Fc) It is a tour of length 201, equal to a lower bound, so it is an optimal tour (201 km).
8
The table shows the least distances, in miles, between six garden centres, A to F, in Hampshire. The least distance between A and C is x miles, where 52 < x < 65
A
B
C
D
E
F
A
−
54
x
14
47
55
B
54
−
72
53
18
12
C
x
72
−
65
74
84
D
14
53
65
−
35
41
E
47
18
74
35
−
10
F
55
12
84
41
10
−
By deleting C, find a lower bound, in terms of x, for the length of a tour of the garden centres.
By deleting B, find a second lower bound in terms of x
State which of the two lower bounds is better, giving a reason.
The tour A - C - B - F - E - D - A has length (143 + x) miles. Write down an interval, in terms of x, that must contain the length, L, of the optimal tour.
7 marks
Show answer
a) 136 + xb) 89 + xc) 136 + x, since it is larger for every xd) 136 + x ≤ L ≤ 143 + x
9
The table shows the least distances, in km, between seven campsites, A to G, in the Lake District. A warden visits every campsite, starting and finishing at A.
A
B
C
D
E
F
G
A
−
32
71
22
77
61
48
B
32
−
39
30
45
34
20
C
71
39
−
63
8
12
23
D
22
30
63
−
62
51
40
E
77
45
8
62
−
18
31
F
61
34
12
51
18
−
16
G
48
20
23
40
31
16
−
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the route.
By deleting A, find a lower bound for the length of the route.
By deleting B, find a second lower bound.
Using your answers, write down the smallest interval that must contain the length, L km, of the optimal route.
9 marks
Show answer
a) A - D - B - G - F - C - E - A, 185 kmb) 140 kmc) 148 kmd) 148 ≤ L ≤ 185
10
The network below shows the cycle paths between six stations, A to F, in Cambridge. The numbers on the arcs are lengths in hundreds of metres.
Complete the table of least distances below.
By deleting A, find a lower bound for the length of a tour of the six stations.
By deleting C, find a second lower bound.
State the better lower bound, giving a reason.
8 marks
Show answer
a) AD = 36, AF = 51, BF = 39, CF = 34b) 87c) 92d) 92 (9200 m), the larger
11
The table shows the least distances, in km, between six farms, A to F, in Devon. The least distance between B and D is x km, where 36 < x < 49
A
B
C
D
E
F
A
−
8
21
44
17
19
B
8
−
13
x
14
11
C
21
13
−
49
27
16
D
44
x
49
−
35
47
E
17
14
27
35
−
25
F
19
11
16
47
25
−
By deleting A, find a lower bound for the length of a tour of the farms.
By deleting D, find a lower bound in terms of x when x < 44, and the lower bound when x ≥ 44
Use the nearest neighbour algorithm, starting at A, to find an upper bound.
The better of the lower bounds in (a) and (b) is 120 km.
Find the value of x and write down an interval that must contain the length, L km, of the optimal tour.
10 marks
Show answer
a) 98 kmb) 81 + x for x < 44; 125 for x ≥ 44c) A - B - F - C - E - D - A, 141 kmd) x = 39; 120 ≤ L ≤ 141
12
A heritage inspector must visit eight castles in Wales, A to H, starting and finishing at A. The table below shows the least driving distances between them, in miles.
By deleting B, and using Prim's algorithm starting at A, find a lower bound for the length of the inspector's route. State the order in which you select the arcs.
Deleting A gives a lower bound of 177 miles and deleting C gives a lower bound of 188 miles.
State the best lower bound, giving a reason.
Use the nearest neighbour algorithm, starting at A, to find an upper bound.
Write down the smallest interval that must contain the length, L miles, of the optimal route.
A colleague claims to have found a route of 198 miles. Explain why the colleague must be wrong.
11 marks
Show answer
a) AD, AE, DC, EG, GH, AF; lower bound 204 milesb) 204 miles, the largestc) A - D - E - G - H - F - B - C - A, 258 milesd) 204 ≤ L ≤ 258e) 198 < 204, the lower bound, and no route can be shorter than a lower bound.
Your score
Answer the questions above and your score appears here.
Every question here is original and written by Robinson Tuition. It follows the Edexcel A-level Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.