The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum_{v\in V}f(u,v)=0$ for every $u\not\in \{s,t\}$ where $s,t$ are the source and sink respectively. I think I get the intuitive idea expressed here, that there should be no accumulation or net loss in any vertex. However, it seems to me this expression actually says "The follow out of u is always 0". Am I confused or is the correct expression, $\forall u\not\in \{s,t\}$
$$\sum_{v\in V}f(u,v)=\sum_{w\in V}f(w,u) $$
Or is it there something about the requirement that $f(u,v)=-f(v,u)$ that takes care of this automatically? And maybe somehow in the summation we don't pay too much attention to the placement of the $u$ in the formula?
1 Answer 1
The definition given in the lectures you've seen is the usual, which can be seen as the conservation of flow through a node, as it follows that flow exiting the node is equal to the flow entering the node. The expression doesn't only consider outgoing flow, as the equation $f(u,v) = -f(v,u)$ means that incoming flow can be described as 'negative' outgoing flow.
Your expression currently just says 'the flow through $u$ is the flow through $u$', which doesn't restrict the flow at all.
A better version of the expression you try to pose is the following:
$\begin{equation} \sum_{v\in V_{in}(u)} f(v,u) = \sum_{v\in V_{out}(u)} f(u,v), \end{equation}$
where $V_{in}(u)$ is the set of nodes $v$ that such that $v\rightarrow u$ is an edge and $V_{out}(u)$ the set of nodes $v$ such that $u\rightarrow v$ is an edge.
It can be easily shown that this equation is equivalent to $\sum_{v\in V} f(u,v) = 0$ when $f(u,v)= -f(v,u)$ for all $u,v\in V$.