0
$\begingroup$

According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents something like $f((u,v))=c$ and $f((v,u))=c$ (where c is the capacity in the original undirected edge) but then that means the original graph has flow $2c$. Could someone prove or explain why the capacity restrictions are still satisfied?

$\endgroup$
1
$\begingroup$

What you describe can happen in a feasible flow. However the net flow across the (undirected) edge $\{u,v\}$ would be $0$. Also, you say that the original graph has flow $2c$, this is false since the amount of flow from a vertex $s$ to a vertex $t$ in a graph is not the sum of the flows across all the edges, but rather the amount of flow leaving $s$ or, equivalently, entering in $t$.

$\endgroup$

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.