A2 June 2019 Q6

EdexcelCurrent spec8 marksFlows in Networks

Figure 2: capacitated directed network from S to T with arcs (lower, upper): SA (7, 9), SC (8, 11), SB (13, 17), CA (3, 5), AE (10, 12), CE (2, 4), BC (0, 4), CG (5, 7), CF (3, 6), BF (3, 5), BD (4, 7), EH (5, 8), EG (3, 5), GH (10, 14), HT (17, 20), GT (4, 7), FG (5, 6), FT (6, 8), DF (1, 2), DT (4, 4); dashed cuts C1 (through SA, SC, BC, BF, BD) and C2 (through EH, EG, CE, CA, SC, BC, BF, DF, DT) — Figure 2

Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid flows from a source, S, to a sink, T.

The numbers \((l, u)\) on each arc represent, in litres per second, the lower capacity, \(l\), and the upper capacity, \(u\), of the corresponding pipe.

Two cuts \(C_1\) and \(C_2\) are shown.

(a) Find the capacity of

(i) cut \(C_1\)

(ii) cut \(C_2\) (2)

(b) Explain why the arcs AE and CE cannot be at their upper capacities simultaneously. (1)

(d) Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams below and give reasons to justify your answer. You should not apply the labelling procedure to find these flows. (4)

Blank copy of the network for the minimum feasible flow — Minimum feasible flow

Blank copy of the network for the maximum feasible flow — Maximum feasible flow

Scheme	Marks	AO
(i) \(C_1 = 9 + 11 + 4 + 5 + 7 = 36\)	1B1	1.1b
(ii) \(C_2 = 8 + 5 - 2 - 3 + 11 + 4 + 5 + 2 + 4 = 34\)	2B1	1.1b
	(2)

Mark scheme (b)

Scheme	Marks	AO
If AE and CE were both full to capacity then \(12 + 4 = 16\) litres per second would flow though E but the maximum capacity of the two arcs out of E (EH and EG) is only \(8 + 5 = 13\) so AE and CE cannot both be full to capacity	1B1	2.4
	(1)

Notes

1B1: Calculates maximum capacity entering E and compares with maximum capacity leaving E. Concludes that maximum capacity into E exceeds maximum capacity out of E.
Condone statements such as ‘flow into E \(= 12 + 4 < 13\) which is the flow out of E’.

Mark scheme (c)

Scheme	Marks	AO
The minimum flow through the arcs AE, CE, CG, FG, FT and DT (which provides a cut for the network) is \(10 + 2 + 5 + 5 + 6 + 4 = 32\) so a minimum of 32 must be flowing through the system so 31 is not possible.	1B1	2.4
	(1)

Notes

1B1: valid reason why the flow in the network cannot be 31 litres per second.

Note: If smallest of \(C_1\) and \(C_2\) in a) is less than 31 then DO NOT allow this mark for deducing that ‘31 > {smallest of answers from a} hence, flow of 31 is not possible’.

Minimum flow of 32: SA 7, SC 10, SB 15, CA 3, AE 10, CE 2, BC 4, CG 5, CF 4, BF 5, BD 6, EH 7, EG 5, GH 11, HT 18, GT 4, FG 5, FT 6, DF 2, DT 4 — Mark scheme (d)

Maximum flow of 34: SA 8, SC 11, SB 15, CA 3, AE 11, CE 2, BC 4, CG 6, CF 4, BF 5, BD 6, EH 8, EG 5, GH 11, HT 19, GT 5, FG 5, FT 6, DF 2, DT 4 — Mark scheme (d)

Scheme	Marks	AO
Attempt to find a flow of 32 using the answer to (c)	1M1	3.4
E.g. Minimum flow of 32	1A1	1.1b
Attempt to augment minimum flow and recognise that from (a) the maximum flow is less than or equal to 34	1B1	2.1
E.g. Maximum flow of 34	2B1	1.1b
	(4)
	(8 marks)