1
$\begingroup$

I have read that Flow network is a directed graph , with no self loops and there is no reverse edges and non negative capacity. However in Residual network ,we allow the reverse edges so we can cancel(subtract) some units from the flow.

My question is why there is no reversed edges in flow networks ?

i understand that it is directed since we need to go from source to sink ,non negative capacity since there is no a negative flow but i don't understand why no reversed edges.

$\endgroup$
  • $\begingroup$ Can you explain or how will you define what is reversed edges in the case of flow network? $\endgroup$ – Apass.Jack Jan 4 at 13:11
  • $\begingroup$ between 2 vertices there is the normal forward edge (u,v) , and another edge (v,u) that goes backward(this is the reversed edge). regardless their capacities @Apass.Jack $\endgroup$ – Abdel-Rahman El-Feraly Jan 4 at 14:00
0
$\begingroup$

Here is your definition of reversed edges in the case of flow network given in your comment.

Between 2 vertices there is the normal forward edge (u,v) , and another edge (v,u) that goes backward(this is the reversed edge). regardless their capacities.

If your definition is used, flow networks may have reversed edges indeed. For example, the flow network (a) in the picture below does have reversed edges between node $v_1$ and $v_2$. The two edges are usually called anti-parallel edges.

Picture is taken from http://www2.hawaii.edu/~nodari/teaching/s18/Notes/Topic-20/Removing-Anti-Parallel-Edges.html, Nodari Sitchinava

However, anti-parallel edges can be eliminated by introducing a new node and two edges having the same capacity as one of the anti-parallel edges. For example, the flow network (a) is equivalent to the flow network (b) in the above picture. Be careful that we can't simply remove the edge from $v_2$ to $v_1$ and subtract 4 from 10 to get 6 as the new capacity for the edge from $v_1$ to $v_2$ because the resulting flow network would not allow us to use only the edge from $v_2$ to $v_1$.

Flow networks without anti-parallel edges are easier to explain and process. It is not surprising if anti-parallel edges are avoided or excluded or disallowed for the sake of simplicity in many situations.


Exercise. Consider a flow network $(V,E,s,t,c)$, and let $e, e'\in E$ be anti-parallel edges. Prove that there exists a maximum flow in which at least one of $e, e'$ has no flow through it.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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