2
$\begingroup$

Let's suppose we have a directed graph $G$ which has at least a pair of vertices $v,w$ such that $(v,w) \in E, (w,v) \in E$.

$e.g:$

enter image description here

In the example, there is an edge going from $C$ to $A$ and viceversa.

So, my question is, what would be the way to model this graph with a residual graph?

$\endgroup$
2
$\begingroup$

The residual graph is not a graph modeling method. It represents how we can change the flow on edges of a graph $G$ in order to increase the total flow when we compute the maximum flow.

The residual capacity used when you construct the residual graph is defined as $$ c_f(u,v) = \begin{cases} c(u,v) - f(u,v) & \text{if $ (u,v) \in E$} \\ f(v,u) & \text{if $ (v,u) \in E$} \\ 0 & \text{otherwise} \end{cases}\ $$

So, we cannot have both $(u,v)$ and $(v,u)$ in $E$ even though the antiparallel edges do not contradict the main network flow properties.

Your graph contains antiparallel edges which you should get rid of before you run a maximum flow algorithm on that graph, e.g., Ford-Fulkerson algorithm.

You could transform this graph into equivalent one with no antiparallel edges as following. You choose one antiparallel edge and "split" it into two edges. For example take $AC$ and introduce a new vertex $F$ and two new edges $AF$ and $FC$ with weights equal to $5$, i.e., $w(AF)=w(FC) = 5$. Similarly for every pair of antiparallel edges in the graph.

$\endgroup$
  • 1
    $\begingroup$ If the edges represent capacities (as is usual with flow networks), there is nothing wrong with antiparallel edges. Were you thinking that the edges reflect the flow, rather than the capacities? Those are two different things, and it seems the question isn't clear about what its graph is supposed to represent. $\endgroup$ – D.W. Aug 4 '17 at 5:45
  • $\begingroup$ @D.W. They are capacities. I remove antiparallel edges in order compute residual capacities. Residual capacity is defined as $cap(u,v)-f(u,v)$ if $(u,v) \in E$ and $f(v,u)$ if $(v,u) \in E$ (Ref: Cormen, and etc.). $\endgroup$ – fade2black Aug 4 '17 at 6:30
  • $\begingroup$ If they are capacities, antiparallel edges are fine; you can still compute the residual graph. You define $c_f(u,v) = c(u,v)-f(u,v)$ if $f(u,v)>0$, else $c_f(u,v) = f(v,u)$ if $f(v,u)>0$, else $c_f(u,v)=0$. $\endgroup$ – D.W. Aug 4 '17 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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