minimum cut, as applied to a directed network flow.
\includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299}
The figure above shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\).
Given that one of these two cuts is a minimum cut,
find a maximum flow pattern by inspection, and show it on the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
Find a second minimum cut for this network.
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\).
State, with a reason, which of these arcs should be added, and the value of the increased flow.