patternMinor
Why in Flow network, there is no reversed edges?
Viewed 0 times
whyflowedgesreversedtherenetwork
Problem
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.
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.
Solution
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.
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.
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.
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.
Context
StackExchange Computer Science Q#102382, answer score: 9
Revisions (0)
No revisions yet.