= Circulation with vertex demands
{title2=$\sum_uf_{uv}-\sum_wf_{vw}=d_v$}
A <flow> on a <directed graph> satisfying <capacity constraints> and a specified net inflow $d_v$ at each <vertex>. Positive $d_v$ denotes consumption and negative $d_v$ supply. Summing all balances cancels each <edge> once as inflow and once as outflow, so $\sum_vd_v=0$ is necessary. With balanced demands and no lower bounds, add a source <edge> of <flow network edge capacity> $-d_v$ into every supply <vertex> and an <edge> of <flow network edge capacity> $d_v$ from each demand <vertex> to a new sink. A <maximum flow> saturating all auxiliary <edges> exists exactly when the demands are feasible.
Back to article page
