D2 June 2011 Q1

EdexcelOld spec10 marksTravelling Salesman

Figure 1: network of six towns. AB 24, AC 11, AD 23, AE 22, BC 8, BE 20, BF 32, CE 9, DE 27, DF 31, EF 17 — Figure 1

The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

(a) By inspection, complete the two copies of the table of least distances in your answer book. (3)

(b) Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou’s route. Write down the route which gives this upper bound. (3)

Mark scheme (a)

Scheme

Marks

	A	B	C	D	E	F
A	-	19	11	23	20	37
B	19	-	8	42	17	32
C	11	8	-	34	9	26
D	23	42	34	-	27	31
E	20	17	9	27	-	17
F	37	32	26	31	17	-

B3, 2, 1, 0

(3)

Notes

The entries to be found are shown in bold.

1B1 One double entry correct

2B1 Two double entries correct

3B1 Three double entries correct

Residual minimum spanning tree CB 8, CE 9, ED 27, EF 17, with dashed arcs AC 11 and AB 19 — Mark scheme (c)

Scheme	Marks
Delete A	M1
RMST weight = 61	A1
Lower bound = 61 + 11 + 19 = 91 km	M1 A1
	(4)
	(10 marks)