7.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{9ca3e12a-63fa-49c9-91fc-eedfb024417a-6_993_1552_312_242}
\end{figure}
Figure 4 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.
- Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 2 in the answer booklet.
- Find the values of \(x\) and \(y\), explaining your method briefly.
- Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\).
Starting with the given feasible flow of 68,
- use the labelling procedure on Diagram 3 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow.
- Show your maximal flow on Diagram 4 and state its value.
- Prove that your flow is maximal.