Flow

A flow is a function $f:E\to R$ where $f(u,v)\ge 0$ is the flow on edge $(u,v)$ with properties:

• Capacity constraints: for each edge $(u,v)\in E$, $0\le f(u,v)\le c(u,v)$
• Flow conservation: for each node $v\in V-\{s,t\}$:
  • The total flow into $v$ is equal to total flow out of $v$ $\begin{array}{rl}\text{flow in}& =\text{flow out}\\ a+b+c& =d+e\\ \sum _{(x,v)\in E}f(x,v)& =\sum _{(v,z)\in E}f(v,z)\end{array}$
  • i.e. net flow into $v$ is equal to $0$ $\begin{array}{rl}\text{net flow into }v& =0\\ a+b+c-d-e& =0\\ \sum _{(x,v)\in E}f(x,v)-\sum _{(v,z)\in E}f(v,z)& =0\end{array}$