2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at \(S\) to a sink at \(T\). Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty.
Fig. 3 shows a flow of 5 litres per second from \(S\) to \(T\).
Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc).
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-3_524_876_717_141}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-3_524_878_717_1046}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{figure}
- Write down the capacity of \(\operatorname { arc } F T\) and of \(\operatorname { arc } D T\). Find the value of the cut that separates the vertices \(S , A , B , C , D , E , F\) from the sink at \(T\).
- (a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along \(S - C - B - F - T\).
(b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time. - Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.