1
$\begingroup$

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?

Thanks in advance :)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! That's tricky. The sources I've read either had the ingoing equals outgoing definition or didn't elaborate on this version. I think this is too subtle to have this being "obvious" in books. Thank you so much for your fast response. $\endgroup$ – Sbls Jul 7 '15 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.