A small confusion in network flows (conservation constraints).

935 Views Asked by At

I'm reading the Handbook of Graph Theory.

enter image description here enter image description here

I guess It says that the sum of the flows going is equal do the sum of flows going back, I'm confused about what is the value of the flow going back, let's take a silly example:

$$\displaystyle \begin{matrix} {}&{}&{\tiny 10}&{}&{}\\ {}&{v}&{\rightarrow}&{w}&{}\\ {\tiny 10}&{\uparrow}&{}&{\downarrow}&{\tiny 10}\\ {}&{s}&{}&{t}&{} \end{matrix}$$

Then taking the only possible edge, I have $10$ going. But I have $0$ going back, isn't? Then it doesn't make sense to use D2 ans say that $10=0$. I am confused here.

1

There are 1 best solutions below

2
On BEST ANSWER

When they write "$(x,y)\in E$" you should visualize this as an arrow starting at $x$ and pointing to $y$. Something like "$x\to y$". Notice that the order that $x$ and $y$ appear in the notation $(x,y)\in E$ is meaningful, unlike in undirected graphs.

Now the conservation constraints are written here $$\sum_{(w,v)\in E} f(w,v)=\sum_{(v,w)\in E} f(v,w) \text{ for each } v\in V-\{s,t\}.$$

This actually means that you have $|V|-2$ different constraints, one for each vertex $v\in V-\{s,t\}$. Each constraint means the following.

Take any vertex $v\in V$ except $s$ and $t$. First, add up the flow values over all edges in $E$ that are pointing to $v$. Call this sum $F_\text{in}(v)$. (This is the left side of the equation in the constraint, i.e., $F_\text{in}(v)=\sum_{(w,v)\in E} f(w,v)$).

Now add up the flow values over all edges in $E$ pointing out of $v$. Call this sum $F_\text{out}(v)$. (This is the ride side of the equation in the constraint).

Then the conservation constraint for $v$ is satisfied if and only if $F_\text{in}(v)=F_\text{out}(v)$.

In your example if you take $v$, there is only one edge pointing into $v$, giving $F_\text{in}(v)=10$ and one edge pointing out of $v$, giving $F_\text{out}(v)=10$. Since $10=10$, the conservation constraint is satisfied for $v$. Next, you have to check that the conservation constraint is satisfied for $w$. Again we have $F_\text{in}(w)=10=F_\text{out}(w)$, and so the conservation constraint is satisfied for $w$. Thus all the conservation constraints are satisfied for your example.