D1 June 2019 Q2

Figure 3: weighted network of roads on nodes A, B, C, D, E, F, G, H, J — Figure 3

[The total weight of the network is 48.2]

A surveyor needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Figure 3. The number on each arc represents the length of that road in miles. To check all the roads, she needs to travel along each road at least once. She wishes to minimise the total distance travelled.

The surveyor’s office is at F, so she starts and ends her journey at F.

(a) Find a route for the surveyor to follow. State your route and its length. You must make your method and reasoning clear. (4)

The surveyor lives at D and wonders if she can reduce the distance travelled by starting from home and inspecting all the roads on the way to her office at F.

(b) By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in the inspection route from D to F. You must make your method and working clear. (5)

(c) Determine which of the two routes, the one starting at F and ending at F, or the one starting at D and ending at F, is longer. You must show your working. (2)

Mark scheme (a)

Scheme	Marks
Pair the two odds nodes: A with H	B1
Repeat arcs AG, GJ, JH	B1
Length = 48.2 + (2.5 + 0.9 + 1.1) = 48.2 + 4.5 = 52.7	B1
e.g. route FAGABFGJGHJHFEJBCDECF	B1
	(4)

Notes

a1B1: CAO (correct pairing of the two odd nodes stated) – this mark may be implied by consideration of the shortest path from A to H (or vice-versa)

a2B1: Correct repeated arcs stated (AG, GJ, JH)

a3B1: CAO (length of 52.7)

a4B1: Correct route: checks – starts and finishes at F, 21 nodes, AG, GJ and JH repeated, A(2), B(2), C(2), D(1), E(2), F(4), G(3), H(2), J(3)

Mark scheme (b)

Scheme	Marks
AD + FH = A(BC)D + F(GJ)H = 6 + 3.7 = 9.7	M1 A1
AF + DH = AF + D(EJ)H = 2.4 + 5.5 = 7.9*	A1
AH + DF = A(GJ)H + D(E)F = 4.5 + 3.8 = 8.3	A1
Repeat arcs AF, DE, EJ and JH	A1
	(5)

Notes

b1M1: Three distinct pairings of nodes A, D, F and H

b1A1: Any one row correct including pairing and total

b2A1: Any two rows correct including pairings and totals

b3A1: All three rows correct including pairings and totals

b4A1: CAO correct arcs clearly (not just in their working) stated: AF, DE, EJ and JH. Do not accept DH, DEJH or DH via E and J

Mark scheme (c)

Scheme	Marks
Route from D to F is longer	B1
Difference = (48.2 + 7.9) – 52.7 = 3.4 or 7.9 – 4.5 = 3.4	B1
	(2)
	11 marks

Notes

c1B1: CAO (oe e.g. F to F is shorter) – dependent on correct repeats in (a) and (b) or clearly implied in (c) (e.g. correct values compared in this part)

c2B1: CAO (difference of 3.4 or comparing 52.7 and 56.1 or comparing 7.9 with 4.5)