D2 June 2005 Q6

EdexcelOld spec16 marksFlows in Networks

Capacitated directed network with sources S1, S2 and sinks T1, T2, capacities and circled initial flows

This figure shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.

(a) On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. (2)

Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.

Diagram 2: the network with the first stage of the labelling procedure, excess capacities and potential backflows on each arc — Diagram 2

(b) Complete the initial labelling procedure in Diagram 2. (2)

(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow, and state the maximal flow. (6)

(d) Show a maximal flow pattern on Diagram 3. (2)

(e) Prove that your flow is maximal. (2)

(f) Describe briefly a situation for which this network could be a suitable model. (2)

Mark scheme (a)

Scheme	Marks
\(SS_1 - 47,\ SS_2 - 87,\ T_1T - 51,\ T_2T - 73\) added to diagram 1	M1 A1
	(2)

Notes

If all 4 nos. zero then M0

M1 4 arcs added correctly + 4 numbers given (diagram 1 only) condone lack of arrows

A1 c.a.o. (diagram 1 only) penalise arrow errors here

(Corrected from the printed mark scheme: the capacities of \(T_1T\) and \(T_2T\) are printed as “\(S_1\)” and “\(T_3\)”; they are \(17 + 34 = 51\) and \(40 + 33 = 73\).)

Mark scheme (b)

Scheme	Marks
\(SS_1\ \underset{\leftarrow 47}{\overset{\rightarrow 0}{}},\quad SS_2\ \underset{\leftarrow 49}{\overset{\rightarrow 38}{}},\quad T_1T\ \underset{\leftarrow 43}{\overset{\rightarrow 8}{}},\quad T_2T\ \underset{\leftarrow 53}{\overset{\rightarrow 20}{}}\)	M1 A1
	(2)

Notes

M1 4 arcs, 2 numbers and 2 arrows \(\rightleftarrows\) per arc

A1 c.a.o.

Mark scheme (c)

Scheme	Marks
e.g. \(S\ S_2\ A\ D\ T_1\ T - 2\) \(S\ S_2\ C\ E\ T_2\ T - 1\) \(S\ S_2\ C\ E\ D\ T_2\ T - 10\) \(S\ S_2\ C\ E\ B\ D\ T_1\ T - 4\)	M1 A4, 3, 2, 1, 0
Maximum flow — 113	B1
	(6)

Notes

M1 2 correct routes + flows found (flow > 10 gets M0) (condone initial f.a. routes only if clearly repeated from new ones)

A4 all flows + routes to 15 more or flow increased above 17 more

A2 \(\geqslant 3\) flows + routes to 11 more or

A1 at least 2 flows + routes found to 5 more

B1 113 c.a.o.

Scheme	Marks
e.g.	M1 A1
	(2)

Mark scheme (e)

Scheme	Marks
Max flow – min cut theorem; cut \(AT_1,\ AD,\ S_1B,\ S_2B,\ BC,\ CE\)	M1 A1
	(2)

Notes

M1 flow of 113 + cut attempted + max flow – min cut theorem referred to (3 out of 4)

A1 c.a.o.

Scheme	Marks
Idea of a directed flow along arcs; from \(S\) to \(T\); through a system/network; practical	B2, 1, 0
	(2)
	(16 marks)