D1 June 2012 Q4

EdexcelOld spec12 marksGraphs & Networks Route Inspection

Figure 3: network of pipes A to K with lengths in metres — Figure 3

[The total weight of the network is 1436 m]

(a) Explain the term valency. (2)

Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe.

Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.

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

Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI. The length of the inspection route must be minimised.

(d) Find the length of the minimum inspection route excluding HI. Justify your answer. (2)

(e) Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI. (2)

Scheme	Marks
The valency of a vertex is the number of edges incident to it.	B2,1,0
	(2)

Mark scheme (b)

Scheme	Marks
DE + HI = 131 + 75 = 206	M1 1A1
DH + EI = 146 + 137 = 283	2A1
DI + EH = 143 + 62 = 205*	3A1
Arcs EH, DF and FI will be traversed twice.	4A1ft
	(5)

Notes

b1M1 Three pairings of their four odd nodes

b1A1 One row correct including pairing and total

b2A1 Two rows correct including pairing and total

b3A1 Three rows correct including pairing and total

b4A1ft Their smallest repeated arcs, (accept DFI).

Scheme	Marks
Route length = 1436 + 205 = 1641(m)	B1ft
	(1)

Mark scheme (d)

Scheme	Marks
Since HI is removed only D and E are odd, So only the route between DE need to be repeated Route length = 1436 – 75 (for HI) + 131 = 1492(m)	M1 A1
	(2)

Notes

d1M1 Aim to include their DE(131) [ft from (b)] and remove HI(75) or 1436+131–75

d1A1 CAO 1492. Must see method though, NMS gets M0.

Mark scheme (e)

Scheme	Marks
Route should start and finish at D and E. E.g. DCFDAEBGEFKIFHJGHE (18 vertices)	M1, A1
	(2)
	(12 marks)

Notes

e1M1 D and E identified as start and finish nodes. We do not have to see a route here.

e1A1 CAO must see a route. 18 vertices; Each of A–K present; 3E’s, 3F’s, 2D’s, 2G’s and 2H’s.