World's most popular travel blog for travel bloggers.

# Flow in a network: Conservation of flow definition

, ,
Problem Detail:

This might be too easy... But I just don't get it.

I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network

$\sum\limits_{w\in V} f(u,w) = 0$ $(\forall u \in V-\{s, t\})$

That implies $\sum\limits_{(u,v)\in E} f(u,v) = \sum\limits_{(v, z)\in E} f(v,z)$

It sounds trivial, but how does that implication work? The flow is 0 when there is no edge. So I think I can rewrite the first sum to:

$\sum\limits_{w\in V} f(u,w) = 0 \iff \sum\limits_{(u,v)\in E} f(u,v) = 0$ for a node $u$

That would result in every flow being zero, wouldn't it? What am I doing wrong?

The short answer is $f(u,v)=-f(v,u)$. Note that the first sum includes both vertices $w$ such that $(u,w) \in E$, as well as vertices $w$ such that $(u,w) \notin E$ but $(w,u) \in E$. Now unpack the implications of the first sum, separating by these two cases, and I think you'll see what happens.

For a more lengthy explanation, this is covered in standard textbooks. Make a trip to a library to check out a few textbooks to find a detailed derivation; or, there are even online algorithm texts.