(i) Let $G$ be a directed network with nodes $N$ and $\operatorname{arcs} A$. Let $S \subset N$ be a subset of the nodes, $x$ be a flow on $G$, and $y$ be the divergence of $x$. Describe carefully what is meant by a cut $Q=[S, N \backslash S]$. Define the arc-cut incidence $e_{Q}$, and the flux of $x$ across $Q$. Define also the divergence $y(S)$ of $S$. Show that $y(S)=x \cdot e_{Q}$.

Now suppose that capacity constraints are specified on each of the arcs. Define the upper cut capacity $c^{+}(Q)$ of $Q$. State the feasible distribution problem for a specified divergence $b$, and show that the problem only has a solution if $b(N)=0$ and $b(S) \leqslant c^{+}(Q)$ for all cuts $Q=[S, N \backslash S]$.

(ii) Describe an algorithm to find a feasible distribution given a specified divergence $b$ and capacity constraints on each arc. Explain what happens when no feasible distribution exists.

Illustrate the algorithm by either finding a feasible circulation, or demonstrating that one does not exist, in the network given below. Arcs are labelled with capacity constraint intervals.

Part II