Robinson Tuition
A-level Decision Mathematics 1 · Edexcel 9FM0 · free Further Maths worksheet

Travelling salesman: lower bounds

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.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

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.

ABCDE
A−29134818
B29−207047
C1320−5631
D487056−55
E18473155−

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.

Deleted vertex methodDeleted vertexRMST weightTwo least arcsLower boundE
3 marks
Show answer
130 km
3

The deleted vertex method is used to find lower bounds for a travelling salesman problem.

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

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

  1. 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.
  2. Hence find a lower bound for the length of a tour of all six towns.
ABCDEFABCDEF-405248426840-555357675255-113216485311-212542573221-466867162546-Deleted vertex methodDeleted vertexRMST weightTwo least arcsLower boundA
5 marks
Show answer
a) BD, DC, CF, DE; weight 101 miles b) 183 miles
5

The table shows the least distances, in km, between six offices, A to F, of a firm in Glasgow.

ABCDEF
A−1958455131
B19−39403218
C5839−426036
D454042−7122
E51326071−50
F3118362250−
  1. By deleting A, find a lower bound for the length of a tour of the six offices.
  2. By deleting E, find a second lower bound.
  3. State the better lower bound, giving a reason.
Deleted vertex methodDeleted vertexRMST weightTwo least arcsLower boundAE
6 marks
Show answer
a) 158 km b) 177 km c) 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.

ABCDEF
A−1930411146
B19−49352529
C3049−653772
D413565−3151
E11253731−48
F4629725148−
  1. Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour of the schools.
  2. By deleting F, find a lower bound for the length of the tour.
  3. Hence write down an interval within which the length, T minutes, of the optimal tour must lie.
Upper boundStartTourLengthALower boundDeleted vertexRMST weightTwo least arcsLower boundF
6 marks
Show answer
a) A - E - B - F - D - C - A, 211 minutes b) 166 minutes c) 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.

  1. By deleting F, and using Prim's algorithm starting at A, find a lower bound for the length of her tour.
  2. Show that the arcs you used in (a) form a tour, and state this tour.
  3. Explain what you can deduce about this tour.
ABCDEFABCDEF-431633526043-412713581641-314861332731-236752134823-656058616765-Deleted vertex methodDeleted vertexRMST weightTwo least arcsLower boundF
7 marks
Show answer
a) 201 km b) F - A - C - D - E - B - F c) 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

ABCDEF
A−54x144755
B54−72531812
Cx72−657484
D145365−3541
E47187435−10
F5512844110−
  1. By deleting C, find a lower bound, in terms of x, for the length of a tour of the garden centres.
  2. By deleting B, find a second lower bound in terms of x
  3. State which of the two lower bounds is better, giving a reason.
  4. 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.
Deleted vertex methodDeleted vertexRMST weightTwo least arcsLower boundCB
7 marks
Show answer
a) 136 + x b) 89 + x c) 136 + x, since it is larger for every x d) 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.

ABCDEFG
A−327122776148
B32−3930453420
C7139−6381223
D223063−625140
E7745862−1831
F6134125118−16
G482023403116−
  1. Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the route.
  2. By deleting A, find a lower bound for the length of the route.
  3. By deleting B, find a second lower bound.
  4. Using your answers, write down the smallest interval that must contain the length, L km, of the optimal route.
Upper boundStartTourLengthALower boundsDeleted vertexRMST weightTwo least arcsLower boundAB
9 marks
Show answer
a) A - D - B - G - F - C - E - A, 185 km b) 140 km c) 148 km d) 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.

  1. Complete the table of least distances below.
  2. By deleting A, find a lower bound for the length of a tour of the six stations.
  3. By deleting C, find a second lower bound.
  4. State the better lower bound, giving a reason.
2117924261981513ABCDEFTable of least distancesABCDEFABCDEF-21174321-92432179-19262419-8154332268-131513-Lower boundsDeleted vertexRMST weightTwo least arcsLower boundACDiagram NOT accurately drawn
8 marks
Show answer
a) AD = 36, AF = 51, BF = 39, CF = 34 b) 87 c) 92 d) 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

ABCDEF
A−821441719
B8−13x1411
C2113−492716
D44x49−3547
E17142735−25
F1911164725−
  1. By deleting A, find a lower bound for the length of a tour of the farms.
  2. By deleting D, find a lower bound in terms of x when x < 44, and the lower bound when x ≥ 44
  3. 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.

  1. Find the value of x and write down an interval that must contain the length, L km, of the optimal tour.
Lower boundsDeleted vertexRMST weightTwo least arcsLower boundAD (x < 44)D (x ≥ 44)Upper boundStartTourLengthA
10 marks
Show answer
a) 98 km b) 81 + x for x < 44; 125 for x ≥ 44 c) A - B - F - C - E - D - A, 141 km d) 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.

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

  1. State the best lower bound, giving a reason.
  2. Use the nearest neighbour algorithm, starting at A, to find an upper bound.
  3. Write down the smallest interval that must contain the length, L miles, of the optimal route.
  4. A colleague claims to have found a route of 198 miles. Explain why the colleague must be wrong.
ABCDEFGHABCDEFGH-4334131450334543-6456511148683464-2139706776135621-1859465514513918-5732375011705957-5866334867463258-2045687655376620-Lower boundsDeleted vertexRMST weightTwo least arcsLower boundBA177C188Upper boundStartTourLengthA
11 marks
Show answer
a) AD, AE, DC, EG, GH, AF; lower bound 204 miles b) 204 miles, the largest c) A - D - E - G - H - F - B - C - A, 258 miles d) 204 ≤ L ≤ 258 e) 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.

All A-level Decision Mathematics 1 topics