5
$\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$
2
  • $\begingroup$ Can you explain or how will you define what is reversed edges in the case of flow network? $\endgroup$
    – John L.
    Commented Jan 4, 2019 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$ Commented Jan 4, 2019 at 14:00

3 Answers 3

9
+50
$\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$
1
  • 1
    $\begingroup$ I would add that a specific reason why textbooks sometimes prefer to assume that there are no anti-parallel edges is that it makes the definition of the residual graph in the Ford-Fulkerson algorithm easier. In particular, with that restriction, an edge (u, w) in the residual graph is a back edge if and only (u, w) is not present in the original graph. $\endgroup$
    – Neal Young
    Commented Apr 4 at 13:08
0
$\begingroup$

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

The answer is that there are reversed edges in flow networks. The definition written is slightly incorrect there. The Wikipedia definition says:

"A network is a directed graph G = (V, E) with a non-negative capacity function c for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). Without loss of generality, we may assume that if (u, v) ∈ E, then (v, u) is also a member of E. Additionally, if (v, u) ∉ E then we may add (v, u) to E and then set the c(v, u) = 0.

If two nodes in G are distinguished – one as the source s and the other as the sink t – then (G, c, s, t) is called a flow network.[1] " https://en.wikipedia.org/wiki/Flow_network

In other words, this tells us that a flow network can have reverse edges, and it would make sense to. How else could we model water pipes that are flatly laid out, where we might not be certain which direction the water will flow through? (Where gravity is not an issue)

What that sort of definition might be getting confused with, is how water can only flow one way. So after simulating the water flow, or finding the max-flow. If you find that you have water flowing from A to B, then it can't be flowing from B to A, in reverse.

However, the question is correct in saying "no self loops" and "non negative capacity."

The other answer posted is also correct, especially the part where we avoid anti-parallel edges for the sake of simplicity. They have a good example there that can be used,

$\endgroup$
0
$\begingroup$

You could have reverse edges in the original flow graph.

When working with flow graphs, the maximum flow is equal to the minimum cut. The minimum cut partitions the vertices of the graph into sets A and B. A contains the source and B contains the sink.

When calculating the capacity between sets A and B you take the sum of the edge capacities for edges going from A to B but not from B to A.

If you included the edges going from B to A in the sum, it would not maximize the flow to the sink.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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