D2 June 2007 Q5

EdexcelOld spec14 marksFlows in Networks

Figure 1: network with the labelling procedure shown on each arc — Figure 1

In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.
The arrow on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.

(a) Add a supersource \(S\), a supersink \(T\) and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs. (3)

(b) Write down the value of the initial flow shown in Figure 1. (1)

(c) Use Figure 2, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow. (5)

(d) Show your flow on a diagram and state its value. (3)

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

Scheme	Marks
	M1 A1 A1
	(3)

Scheme	Marks
103	B1
	(1)

Scheme	Marks
e.g. \(S\,B\,E\,G\,I\,L\,T - 3\) \(S\,B\,E\,D\,F\,K\,T - 5\) \(S\,B\,E\,H\,J\,G\,D\,F\,K\,T - 4\) \(S\,B\,E\,G\,D\,F\,I\,L\,T - 9\)	M1 A4, 3, 2, 1, 0
	(5)

Scheme	Marks
e.g.	M1 A1 A1
Flow value 124 (given)
	(3)

Scheme	Marks
Max flow = min cut cut through AB, BD, DE, EG, HJ	M1 A1
	(2)
	(14 marks)