World's most popular travel blog for travel bloggers.

Flow in a network: Conservation of flow definition

, , No Comments
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:

$\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 :)

Asked By : Sbls
Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback