D2 January 2006 Q7
7.
(a) Define the terms
(i) cut,
(ii) minimum cut,
as applied to a directed network flow. (2)
The figure above 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. (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,\ C_2 = 673\) | B1, B2, 0 |
| (3) |
| Scheme | Marks |
|---|---|
e.g.  | M1 A1 A1 |
| O = saturated – = compulsory | |
| (3) |
| Scheme | Marks |
|---|---|
| AC, CD, GF, FT | B1 |
| (1) |
| Scheme | Marks |
|---|---|
| DE would not allow any further flow into EF | B1, 1, 0 |
| DG would cross both minimum cuts – D can take extra flow, G can accept it. Flow increased by 86 to 759 (accept either number) | |
| (2) | |
| (11 marks) |
Notes
(Corrected from the printed mark scheme: the increase is printed as 8.6; it is \(759 - 673 = 86\).)