Flow (source code)
= Flow
{title2=$\theta$}
= Network flow
{synonym}
In a finite <directed graph> $G=(V,E)$ with distinct source and sink <vertices> $s,t$, a <flow> records an amount $f_{uv}$ on each original <directed edge>. For a <feasible flow> in a <flow network>, these amounts satisfy the <capacity constraints> $0\leq f_{uv}\leq c_{uv}$ and <flow conservation> at every <vertex> other than $s,t$.<Algorithms, 4th edition by Robert Sedgewick and others/FlowEdge.java>[Algorithms, 4th edition by Robert Sedgewick and others; Sedgewick and Wayne, FlowEdge.java, class documentation and capacity/flow constructor: nonnegative amount on an original directed edge, bounded by capacity]{ref}
The antisymmetric convention records signed net amounts instead:
$$
\theta_{uv}=f_{uv}-f_{vu},\qquad \theta_{vu}=-\theta_{uv},\qquad
\operatorname{div}\theta(v)=\sum_{w\in V}\theta_{vw}=0\quad(v\notin\{s,t\}),
$$
taking missing <edge> amounts as zero. The paired signs describe one net transfer, rather than two independent transfers.<Graph Theory by Reinhard Diestel/Flows (author-hosted chapter preview)>[Graph Theory by Reinhard Diestel; Diestel, Flows, §6.2, conditions F1 and F2′, printed p. 158: antisymmetry and conservation at nonterminal vertices]{ref}
For example, if separate original <directed edges> $u\to v$ and $v\to u$ carry $3$ and $1$, their net amount is $\theta_{uv}=2$. This signed record loses the separate amounts: $f_{uv}=2$, $f_{vu}=0$ would give the same net amount. When checking <capacity constraints> on actual <edges>, keep the original amounts or specify the signed bounds carefully; when summing <flow conservation>, either record gives the same <divergence of a flow>.
For the running <flow network>, choose the original <edge> amounts
$$
(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(3,2,1,2,3)
=(c_{sa},c_{sb},c_{ab},c_{at},c_{bt}).
$$
Every <capacity constraint> holds. At $a$, incoming <flow> $3$ equals outgoing <flow> $1+2$; at $b$, incoming <flow> $2+1$ equals outgoing <flow> $3$. This <feasible flow> has <flow value> $5$, computed at $s$ or $t$.
\Image[/network-flow-conservation-ledger.png]
{title=An original-edge <flow> ledger verifies <capacity constraints>, <flow conservation> and <flow value> five}
The total of all five <edge> amounts is $11$, but the <flow value> is $5$. A unit passing through several <edges> appears several times in that total. Concretely, route $2$ units along each of the <directed paths> $s\to a\to t$ and $s\to b\to t$, and $1$ along $s\to a\to b\to t$. Their delivered amounts sum to $2+2+1=5$, while their <edge> usages sum to $2\cdot2+2\cdot2+1\cdot3=11$. The <cut of a flow network> $S=\{s\}$ certifies that this delivery rate is already a <maximum flow>.
<Flow conservation> is useful because it makes a local ledger predict a global delivery rate: intermediate <vertices> only redistribute the resource. An additional <network circulation> can change the individual <edge> amounts without changing the <flow value>. Counting net delivery rather than total <edge> usage prevents such recirculation from masquerading as increased output.
Back to article page
