D2 June 2011 Q5

EdexcelOld spec15 marksFlows in Networks

5.

Figure 2: capacitated directed network from S to T through A to H, with the capacity on each arc
Figure 2

Figure 2 shows a capacitated directed network. The number on each arc is its capacity.

Figure 3: initial flow through the same network, with flows a on FG, b on HG and c on HT
Figure 3

Figure 3 shows an initial flow through the same network.

(a) State the values of flows \(a\), \(b\) and \(c\), and the value of the initial flow. (4)
(b) By entering values along HG, HT and FG, complete the labelling procedure on Diagram 1 in the answer book. (2)
(c) Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (4)
(d) State the value of the maximum flow through the network. (1)
(e) Show your maximum flow on Diagram 2 in the answer book. (2)
(f) Prove that your flow is maximal. (2)
‹ Previous25 of 42 in Flows in NetworksNext ›