= Solution
Write <flow balance> using the positive-inflow convention
$$
\sum_{u:uv\in E}f_{uv}-\sum_{w:vw\in E}f_{vw}=d_v.
$$
Remove the <lower bounds on network flow> by writing $f_{uv}=\ell_{uv}+x_{uv}$, where only $\ell_{BC}=4$ is nonzero. Then $0\leq x_{uv}\leq c_{uv}-\ell_{uv}$, and its required <flow balance> is
$$
d'_v=d_v-\left(\sum_u\ell_{uv}-\sum_w\ell_{vw}\right).
$$
In the order $A,B,C,D$, the lower-bound contribution is $(0,-4,4,0)$, so
$$
(d'_A,d'_B,d'_C,d'_D)=(-6,1,0,5).
$$
The resulting <flow network edge capacities> are
$$
c'_{AB}=5,\quad c'_{AC}=2,\quad c'_{BC}=5,\quad c'_{BD}=3,\quad c'_{CD}=5.
$$
Add 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$.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/advanced-data-structures-2015-extended-flow.png]
{title=Extended <flow network> after removing the lower bound; labels show final <flow> divided by <flow network edge capacity>}
{description=The auxiliary <edges> are blue. The displayed <flow> saturates the auxiliary source and sink <edges>, certifying that all adjusted demands are met. The original <edge> $BC$ regains its four-unit lower bound only after this auxiliary problem is solved.}
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.
|| Step
|| <Augmenting path>
|| Added <flow>
|| Total <flow value>
| $1$
| $s\to A\to B\to t$
| $\min(6,5,1)=1$
| $1$
| $2$
| $s\to A\to B\to D\to t$
| $\min(5,4,3,5)=3$
| $4$
| $3$
| $s\to A\to C\to D\to t$
| $\min(2,2,5,2)=2$
| $6$
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 obtain
$$
\boxed{(f_{AB},f_{AC},f_{BC},f_{BD},f_{CD})=(4,2,4,3,2).}
$$
All original <capacity constraints> hold, and $f_{BC}=4$ meets its lower bound. The net inflows at $A,B,C,D$ are respectively
$$
-4-2=-6,\qquad 4-4-3=-3,\qquad 2+4-2=4,\qquad 3+2=5.
$$
\b[The original network therefore admits a feasible <circulation with vertex demands>.]
Back to article page
