1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a9f21789-1c5b-42f5-9c5a-3b29d9346c46-02_751_1557_214_255}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent a feasible flow from S to T .
- Find the value of \(x\).
- Find the value of \(y\).
- List the saturated arcs.
Two cuts, \(C _ { 1 }\) and \(C _ { 2 }\), are shown in Figure 1.
- Find the capacity of
- \(C _ { 1 }\)
- \(\mathrm { C } _ { 2 }\)
- Write down a flow-augmenting route, using the arc CF, that increases the flow by two units.
Given that the flow through the network is increased by two units using the route found in (d), (e) prove that this new flow is maximal.