D1 June 2016 Q6

Figure 5: weighted network of corridors with vertices A to L — Figure 5

[The total weight of the network is 384]

Figure 5 models a network of corridors in an office complex that need to be inspected by a security guard. The number on each arc is the length, in metres, of the corresponding section of corridor.

Each corridor must be traversed at least once and the length of the inspection route must be minimised. The guard must start and finish at vertex A.

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

It is now possible for the guard to start at one vertex and finish at a different vertex. An inspection route that traverses each corridor at least once is still required.

(b) Explain why the inspection route should start at a vertex with odd degree. (2)

The guard decides to start the inspection route at F and the length of the inspection route must still be minimised.

(d) State a possible route and its length. (2)

Mark scheme (a)

Scheme	Marks
B(AD)E + F(J)H = 45 + 30 = 75*	M1
B(CK)F + E(DG)H = 50 + 35 = 85	A1 (2 correct)
B(CKJ)H + E(DGHJ)F = 60 + 65 =125	A1 (3 correct)
Arcs BA, AD, DE, FJ and JH will be traversed twice	A1
Route length = 384 + 75 = 459 (metres)	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: BA, AD, DE, FJ, JH. Accept BADE, FJH or BE via A and D, FH via J. Do not accept BE, FH

a4A1ft: Correct answer of 459, or 384 + their smallest repeat out of a choice of at least two totals seen

Mark scheme (b)

Scheme	Marks
e.g. if we start at an odd vertex we will finish at another odd vertex. This removes the need to repeat the route between them. So we just have to consider one repeated route rather than two	B2, 1, 0
	(2)

Notes

b1B1: One of (i) finishing at an odd vertex (ii) only having to repeat one route/pairing/pair/path (but not ‘repeat only one arc’) rather than two or having one less route/pairing/pair/path to repeat (but not an argument based only on arcs e.g. ‘one less arc to repeat’ or ‘it reduces the number of arcs’)

b2B1: Correct complete argument – including both (i) and (ii) from b1B1 (so B0B1 is not possible in (b))

Mark scheme (c)

Scheme	Marks
We only have to repeat one pair of odd vertices which does not include F (BE = 45, EH = 35, BH = 60)	M1
EH is the smallest of the repeat so repeat EH (ED, DG, GH) and therefore the guard should finish at B	A1
	(2)

Notes

c1M1: Identifies the need to repeat one route of BE(45), EH(35), BH(60), which does not include F (maybe implicit) or a general comment to repeat one route that does not include F

c1A1: Identifies EH (but not just 35) as the least of those paths not including F, and B as the position of the finishing vertex. Note that they must either explicitly state that EH is the least not including F (just stating that EH is the least is A0) or they list the three pairings (BE, EH, BH) and only these three pairings in this part and state that EH is the least

Mark scheme (d)

Scheme	Marks
Route e.g. FJKFCKLJHGHEDGDECBDAB	B1
The length of the route is 419 (metres)	B1ft
	(2)
	(11 marks)

Notes

d1B1: Any correct route – checks: start at F and finishes at B, 21 vertices (repeats ED, DG, GH, and node A appears 1, B(2), C(2), D(3), E(2), F(2), G(2), H(2), J(2), K(2), L(1))

d2B1ft: Correct answer of 419 or 384 + their EH (i.e. the least route that does not include F – so their smallest of BE, EH, BH – must be their smallest value (usually from (a)) not what they state/think is their smallest value). This mark is dependent on the M mark in (a)