D2 June 2017 Q6

EdexcelOld spec12 marksFlows in Networks

6.

Figure 1: capacitated directed network from S to T through A to G with capacities, initial flows in circles and cut C1
Figure 1

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

(a) State the value of the initial flow. (1)
(b) State the capacity of cut \(C_1\) (1)
(c) Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along AC, SB, BE, DE and FG. (2)
(d) Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (4)
(e) Draw a maximal flow pattern on Diagram 2 in the answer book. (2)
(f) Prove that your flow is maximal. (2)
‹ Previous17 of 42 in Flows in NetworksNext ›