D2 June 2009 Q4

EdexcelOld spec5 marksFlows in Networks

4.

Figure 1: capacitated network from S to T through A, B, C, D, E, F, G with capacities, initial flows in circles, and cuts C1 and C2
Figure 1

Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers in circles represent an initial flow from S to T.

Two cuts C\(_1\) and C\(_2\) are shown in Figure 1.

(a) Find the capacity of each of the two cuts. (2)
(b) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow. (3)
‹ Previous27 of 42 in Flows in NetworksNext ›