D1 January 2006 Q4
4.
(a) Define the terms
(i) cut,
(ii) minimum cut,
as applied to a directed network flow. (2)
Figure 4 shows a capacitated directed network and two cuts \(C_1\) and \(C_2\). The number on each arc is its capacity.
(b) State the values of the cuts \(C_1\) and \(C_2\). (3)
Given that one of these two cuts is a minimum cut,
(c) find a maximum flow pattern by inspection, and show it on the diagram in the answer book. (3)
(d) Find a second minimum cut for this network. (1)
In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
(e) State, with a reason, which of these arcs should be added, and the value of the increased flow. (2)
| Scheme | Marks |
|---|---|
| (i) A cut is a division of the vertices of a flow network into 2 sets, one containing the source(s) and the other containing the sink(s). | B1 |
| (ii) A cut whose capacity is least | B1 |
| (2) |
| Scheme | Marks |
|---|---|
| \(C_1 = 1038,\quad C_2 = 673\) | B1, B2,0 |
| (3) |
| Scheme | Marks |
|---|---|
e.g. | M1 A1 A1 |
| (3) |
| Scheme | Marks |
|---|---|
| \(AC,\ CD,\ GF,\ FT\) | B1 |
| (1) |
| Scheme | Marks |
|---|---|
| \(DE\) would not allow any further flow into \(EF\) \(DG\) would cross both minimum cuts – \(D\) can take extra flow, \(GT\) can accept it. Flow increases by 86 to 759 (accept either number) | B2,1,0 |
| (2) | |
| (11 marks) |