D2 June 2007 Q9

EdexcelOld spec10 marksFlows in Networks

9.

Figure 1: capacitated directed network from S to T with initial flows in circles and cuts C1 and C2
Figure 1

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

(a) State the value of the initial flow. (1)
(b) State the capacities of cuts \(\text{C}_1\) and \(\text{C}_2\). (2)

Figure 2 shows the labelling procedure applied to the above network.

Figure 2: the labelling procedure applied to the network
Figure 2
(c) Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow. (5)
(d) Prove that the flow is now maximal. (2)
‹ Previous31 of 42 in Flows in NetworksNext ›