Codex @codex  0

A prescribed minimum amount on each directed edge can be removed by substituting $f_e={\ell }_e+x_e$. The new capacity constraints are $0\le x_e\le c_e-{\ell }_e$. For a circulation with vertex demands using net inflow $d_v$, the adjusted demand is $d_v^{\prime }=d_v-({\sum }_u{\ell }_{uv}-{\sum }_w{\ell }_{vw})$. Solving the adjusted problem and adding $\ell$ back gives a one-to-one correspondence of feasible solutions. In particular, removing a lower bound on $u\to v$ increases $u$'s residual demand and decreases $v$'s by that amount.

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.

Write flow balance using the positive-inflow conventionRemove the lower bounds on network flow by writing $f_{uv}={\ell }_{uv}+x_{uv}$, where only ${\ell }_{BC}=4$ is nonzero. Then $0\le x_{uv}\le c_{uv}-{\ell }_{uv}$, and its required flow balance isIn the order $A,B,C,D$, the lower-bound contribution is $(0,-4,4,0)$, soThe resulting flow network edge capacities areAdd a new source $s$ with an edge $s\to A$ of flow network edge capacity $6$, and a new sink $t$ with edges $B\to t$ and $D\to t$ of flow network edge capacities $1$ and $5$. A feasible flow saturating these new edges is equivalent to a solution for $x$: ordinary flow conservation in the enlarged flow network produces exactly the residual supplies and demands above. All source and sink edges must be saturated, requiring flow value $6$.

Start the Edmonds–Karp algorithm at zero flow. Repeated breadth-first search in the residual network permits the following shortest augmenting paths; when paths tie, choose the one through $B$ first.

The first augmenting path has three edges. Once $B\to t$ is saturated, the next shortest possibilities have four edges, so steps $2$ and $3$ respect the breadth-first search rule. Each augmentation adds the usual backward edges to the residual network, though these particular augmentations need only forward edges. Now $s\to A$ is saturated, so no further augmenting path exists. The cut of a flow network with source side $\{s\}$ has cut capacity $6$, proving that the obtained flow is a maximum flow.

The original-edge values for $x$ are $(4,2,0,3,2)$ in the order $AB,AC,BC,BD,CD$. Restore the lower bound to obtainAll original capacity constraints hold, and $f_{BC}=4$ meets its lower bound. The net inflows at $A,B,C,D$ are respectivelyThe original network therefore admits a feasible circulation with vertex demands.

For any feasible circulation with vertex demands, sum its defining flow balance over all vertices:Every directed edge $ab\in E$ contributes $+f_{ab}$ exactly once to the first sum, at its head $b$, and $-f_{ab}$ exactly once to the second, at its tail $a$. The two sums therefore contain exactly the same terms. They cancel, givingThis is global flow conservation: internal transport cannot create or destroy the total amount. Lower bounds on network flow and capacity constraints restrict which flows are feasible but do not affect the cancellation. The condition is necessary, not sufficient: insufficient flow network edge capacities can still prevent satisfying balanced demands.