D1 January 2008 Q3

Figure 4: network of roads with vertices A to G and lengths in km — Figure 4

Figure 4 models a network of roads in a housing estate. The number on each arc represents the length, in km, of the road.

The total weight of the network is 11 km.

A council worker needs to travel along each road once to inspect the road surface. He will start and finish at A and wishes to minimise the length of his route.

(a) Use an appropriate algorithm to find a route for the council worker. You should make your method and working clear. State your route and its length. (6)

A postal worker needs to walk along each road twice, once on each side of the road. She must start and finish at A. The length of her route is to be minimised. You should ignore the width of the road.

(b)

(i) Explain how this differs from the standard route inspection problem. (1)

(ii) Find the length of the shortest route for the postal worker. (2)

Mark scheme (a)

Scheme	Marks
CD + FG = 0.7 + 0.6 = 1.3 *	M1 A1
CF + DG = 0.5 + 0.9 = 1.4	A1
CG + DF = 1.1 + 0.5 = 1.6	A1
repeat CD and FG
A possible route e.g. A C D C F G F D G E D A E B A	A1
length: 11 + 1.3 = 12.3 km	A1ft
	(6)

Notes

Q3(a) 1M1 3 distinct pairings of their 4 odd nodes

1A1 one line correct (condone missing total)

2A1 2 lines correct including totals

3A1 All three lines correct including totals

4A1 15 letters, repeat CD and FG, start/finish A, A to G there.

5A1ft 11+ thier minimum

Scheme	Marks
(i) Each arc has to be traversed twice	B1
	(1)
(ii) \(2 \times 11 = 22\) km	B2, 0
	(2)
	(9 marks)