D1 June 2013 Q5

Figure 4: railway network A to H with lengths in miles — Figure 4

[The total weight of the network is 344 miles]

Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway.

Sophie needs to travel along each section to check that it is in good condition.

She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.

(a) Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (5)

(b) Write down a possible shortest inspection route, giving its length. (2)

Sophie now decides to start the inspection route at E. The route must still traverse each arc at least once but may finish at any vertex.

(c) Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route. (3)

Mark scheme (a)

Scheme	Marks
AB + DE = 44 + 30 = 74*	M1
AD + BE = 42 + 35 = 77 AE + BD = 39 + 38 = 77	A3.2.1.0
Repeat arcs AC, BC and DE	A1
	(5)

Notes

a1M1 Three distinct pairings of their four odd nodes

a1A1 Any one row correct including pairing and total

a2A1 Any two rows correct including pairing and total

a3A1 All three rows correct including pairing and total

a4A1 CAO correct arcs identified AC, BC and DE. Accept ACB or AB via C (check to see if via C appears in working) but do not accept AB for this mark

Mark scheme (b)

Scheme	Marks
E.g. ABCADCBEDFGDEGHECA (18 nodes)	B1
Length: 344 + 74 = 418	B1ft
	(2)

Notes

b1B1 Any correct route (checks: eighteen nodes (or seventeen arcs), the route starts and ends at A, pairings AC, BC and DE appear twice in the route and that every letter (A to H inclusive) appears at least once).

b2B1ft correct answer of 418 or 344 + their least out of a choice of at least two totals given in part (a)

Mark scheme (c)

Scheme	Marks
One of AB (44), AD (42) or BD (38) will still have to be repeated.	M1
BD(38) is the shortest	A1
So start at E and finish at A, route length now is 344 + 38 = 382	DA1
	(3)
	(10 marks)

Notes

c1M1 Either identifies the need to repeat one pairing which does not include E (could list potential repeats) or identifies the need to repeat BD (or 38).

c1A1 Identifies the need to repeat one pairing which does not include E and this is BD (38) because it is the least. To score the first two marks the candidate must make it clear that they need to repeat BD because it has the least weight of those pairings that do not include E.

c2DA1 correct finishing point (A) and length (382). This mark is dependent on them identifying BD (38) as the repeat.