D1 January 2008 Q6

EdexcelOld spec13 marksFlows in Networks

(a) Define the term ‘cut’ as it applies to a directed network. (2)

Figure 6: capacitated directed network from S to T with capacities and initial flows in circles — Figure 6

Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

(b) Complete the labelling procedure on Diagram 2 in your answer book by entering values along CE, EG, HT and GT. (2)

(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow. (4)

(d) Show a maximal flow pattern on Diagram 3 in your answer book. (2)

(e) State the value of the maximum flow through the network. (1)

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

Mark scheme (a)

Scheme	Marks
A cut divides the vertices into two sets, one set containing the source(s) and the other the sink(s).	B2, 1, 0
	(2)

Notes

Q6(a) 1B1 Close, bod, probably 2 out of three points below

2B1 Good complete answer, 2 ‘sets’; source and sink seperated; vertices

Scheme	Marks
	M1 A1
	(2)

Mark scheme (c)

Scheme	Marks
E.g. SBACEGT – 9	M1 A1
SBADGEHT – 1	A1
SBFEHT – 3	A1
	(4)

Notes

(c) 1M1 1 correct route and a flow value stated. Any flow>9 gets M0

1A1 1 valid route with valid flow

2A1 2 distinct valid routes with valid flows found to >3

3A1 All routes and flows found to 13

Routes
Do not use: SA or BC
Increases needed for solution:
(NOTE treat back flows as negative e.g. EG+9 and GE+1 gives EG+8)

SB + 13	AC+9	AD+1	BA+10	BF+3
CE+9	DG+1	EG+8	EH+4	GT+9

Scheme	Marks
Max flow – min cut theorem cut through AD, AC, BC, EF, FH	M1 A1
	(2)
	(13 marks)