D1 June 2014 Q3

Figure 1: network of forest tracks A to M with lengths in km — Figure 1

[The total weight of the network is 451]

Figure 1 models a network of tracks in a forest that need to be inspected by a park ranger. The number on each arc is the length, in km, of that section of the forest track.

Each track must be traversed at least once and the length of the inspection route must be minimised. The inspection route taken by the ranger must start and end at vertex A.

(a) Use the route inspection algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear. (5)

(b) State the number of times that vertex J would appear in the inspection route. (1)

The landowner decides to build two huts, one hut at vertex K and the other hut at a different vertex. In future, the ranger will be able to start his inspection route at one hut and finish at the other. The inspection route must still traverse each track at least once.

(c) Determine where the other hut should be built so that the length of the route is minimised. You must give reasons for your answer and state a possible route and its length. (4)

Mark scheme (a)

Scheme	Marks
D(A)E + F(J)K = 35 + 15 = 50* D(HJ)F + E(FJ)K = 24 + 40 = 64 D(HJ)K + EF = 33 + 25 = 58	M1 A1 (2 correct) A1 (3 correct)
Arcs DA, AE, FJ, JK will be traversed twice	A1
Route length = 451 + 50 = 501 (km)	A1ft
	(5)

Notes

a1M1 Three distinct pairings of the correct four odd nodes.

a1A1 Any two rows correct including pairings and totals.

a2A1 All three rows correct including pairings and totals.

a3A1 CAO correct arcs clearly (not just in their working) stated: DA, AE, FJ, JK. Accept DAE, FJK or DE via A, FK via J. Do not accept DE, FK.

a4A1ft The correct answer of 501 or 451 + their smallest repeat out of a choice of at least two totals seen.

Scheme	Marks
Vertex J would appear 3 times in the shortest inspection route	B1
	(1)

Mark scheme (c)

Scheme	Marks
We only have to repeat one pair of odd vertices which does not include vertex K (DE = 35, DF = 24, EF = 25)	M1
DF is the smallest of the three so repeat DF (DH, HJ, JF) and therefore the other hut should be built at E	A1
Route e.g. EADEHDHJFBEFCGFJHLGKJLMK	A1
The length of the route is 475 (km)	A1ft
	(4)
	(10 marks)

Notes

c1M1 Identifies the need to repeat one pairing not including K (maybe implicit) or listing of possible repeats – this mark is dependent on scoring the M mark in (a). Stating any pairing that does not include K is sufficient for this mark.

c1A1 Identifies DF as the least of those pairings not including K and E as the position of the other hut. They have to explicitly state that DF is the least pairing that does not include K or they can list all three pairings (DE, DF, EF) and then say DF is the smallest as this implicitly implies that they are considering only pairings that do not include K.

c2A1 Any correct route (checks: starts at E and finishes at K (or vice-versa), 24 vertices (D, G, L appear twice and E, F, H, J appear three times and every other letter appears at least once).

c3A1ft Correct answer of 475 or 451+ their DF (i.e. the least pairing that does not include K – so their smallest of DE, DF or EF).