(i) Let $G$ be a directed network with nodes $N$, arcs $A$ and capacities specified on each of the arcs. Define the terms feasible flow, divergence, cut, upper and lower cut capacities. Given two disjoint sets of nodes $N^{+}$and $N^{-}$, what does it mean to say that a cut $Q$ separates $N^{+}$from $N^{-}$? Prove that the flux of a feasible flow $x$ from $N^{+}$to $N^{-}$is bounded above by the upper capacity of $Q$, for any cut $Q$ separating $N^{+}$from $N^{-}$.

(ii) Define the maximum-flow and minimum-cut problems. State the max-flow min-cut theorem and outline the main steps of the maximum-flow algorithm. Use the algorithm to find the maximum flow between the nodes 1 and 5 in a network whose node set is $\{1,2, \ldots, 5\}$, where the lower capacity of each arc is 0 and the upper capacity $c_{i j}$ of the directed arc joining node $i$ to node $j$ is given by the $(i, j)$-entry in the matrix

$$\left(\begin{array}{ccccc} 0 & 7 & 9 & 8 & 0 \\ 0 & 0 & 6 & 8 & 4 \\ 0 & 9 & 0 & 2 & 10 \\ 0 & 3 & 7 & 0 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$$

[The painted-network theorem can be used without proof but should be stated clearly. You may assume in your description of the maximum-flow algorithm that you are given an initial feasible flow.]