D2 June 2018 Q4

EdexcelOld spec12 marksFlows in Networks

Figure 1: network from S to T through A to H with excess capacities and potential backflows on each arc — Figure 1

Figure 1 represents a system of pipes through which fluid can flow from the source node, S, to the sink node, T. The labelling procedure has been applied to Figure 1, and the numbers on the arrows, either side of each arc, show the excess capacities and potential backflows.

Currently, no fluid is flowing through the system.

(a) Calculate the capacity of the cut that passes through arcs GT, EG, DE, BE, FE and FH. (1)

(b) Explain why arc GT can never be full to capacity when fluid is flowing through the system. (1)

(c) Apply the labelling procedure to Diagram 1 in the answer book to show the maximum flow along SBET. State the amount that can flow along this route. (2)

(d) Use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (4)

(e) State the maximum flow through the system and find a cut to show that this flow is maximal. (2)

(f) Show the maximum flow on Diagram 2 in the answer book. (2)

Scheme	Marks
Capacity of cut = 7 + 4 + 11 + 1 + 1 = 24	B1
	(1)

Mark scheme (b)

Scheme	Marks
The capacity of arc DG is 3 and the capacity of arc EG is also 3 and so the maximum that can flow in GT is 6 < 7 (the capacity of arc GT) and so GT cannot be full to capacity	B1
	(1)

Notes

b1B1: CAO – max. flow into G is 6, max flow out of G is 7 – answer must be numerical in nature (must contain 6 and 7)

Figure 1 repeated for reference — Mark scheme (d)

Maximum flow of 13: SA 3, SB 5, SC 5, CB 3, CF 2, AB 0, AD 3, BE 8, BF 0, FE 1, FH 1, DE 2, DG 1, EG 3, ET 5, EH 3, GT 4, HT 4 — Mark scheme (f)

Scheme	Marks
e.g.	M1 A1
	(2)
	12 marks

Scheme	Marks
Max flow is 13	B1
Cut through SA, SB, CB, BF, FE and FH (has a capacity of 13)	B1
	(2)