 Solution

A flow network is a finite directed graph $G=(V,E)$ with nonnegative flow network edge capacities $c_e$, together with distinct source and sink vertices $s,t$. A feasible flow in the nonnegative directed-edge convention is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints and flow conservation:Its flow value is the net outflow at the source,which equals the net inflow at the sink by flow conservation.

A cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity counts only directed edges leaving $S$:The net flow across the cut of a flow network subtracts flow on edges returning into $S$, and equals $|f|$.

For the following parts, a circulation with vertex demands has no exceptional source or sink in the original directed graph. Instead it satisfies net inflow minus net outflow equal to $d_v$ at every vertex. Thus positive demands consume flow, and negative demands supply flow.