patternMinor
Residual graph of a graph with bidirectional edges?
Viewed 0 times
residualedgesgraphwithbidirectional
Problem
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:$
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?
$e.g:$
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#79674, answer score: 2
Revisions (0)
No revisions yet.