D2 June 2005 Q9

EdexcelOld spec14 marksFlows in Networks

Capacitated directed network from S to T through A, B, C, D, E, F

This diagram shows a capacitated directed network. The number on each arc is its capacity.

(a) State the maximum flow along

(i) \(SADT\),

(ii) \(SCET\),

(iii) \(SBFT\). (2)

(b) Show these maximum flows on Diagram 1. (1)

Take your answer to part (b) as the initial flow pattern.

(c)

(i) Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2. List each flow-augmenting route you use, together with its flow. (5)

(ii) Draw your final flow pattern on Diagram 3. (2)

(iii) Prove that your flow is maximal. (3)

(d) Give an example of a practical situation that could have been modelled by the original network. (1)

Labelling procedure on Diagram 2 with excess capacities and backflows — Mark scheme (c)

Final flow pattern of 40 — Mark scheme (c)

Scheme	Marks
\(SADT - 8\qquad SCET - 11\qquad SBFT - 9\)	B2, 1, 0
	(2)

Scheme	Marks
	B1
	(1)

Scheme	Marks
(i)	M1 A1
e.g. \(S\,A\,C\,D\,T - 2\qquad S\,C\,F\,T - 6\) \(S\,A\,C\,E\,F\,T - 3\qquad S\,A\,C\,F\,T - 1\) max flow 40	A1 A1
	(5)
(ii) eg.	M1 A1
	(2)
(iii) Max flow – min cut theorem	M1
cut \(AD,\ CD,\ DE,\ ET,\ CF,\ BC,\ SB\) ie \(\{S\ A\ C\ E\}\ \{B\ D\ F\ T\}\)	A2, 0
	(3)

Scheme	Marks
Idea of a directed flow through a system of arcs from \(S\) to \(T\) practical	B1
	(1)
	(14 marks)