8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge.
\includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-22_743_977_404_536}
- Find the maximum flow along each of the routes \(A B E H , A C F H\) and \(A D G H\) and enter their values in the table on Figure 4 opposite.
- Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
- State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
- Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
| Route | Flow |
| \(A B E H\) | |
| \(A C F H\) | |
| \(A D G H\) | |
| |
| |
| |
| |
| |
| |
| |
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
\end{figure}
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
\end{figure}
\includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}