2
$\begingroup$

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent to sending -x units from B to A, so we add a back edge from B to A of capacity x units. And the FF algorithm can send a flow of x units from B to A in the future. But the property of a directed graph is that you can go from A to B and not from B to A. As an analogy let me take the traffic network and say the path from A to B is one-way. Adding a back edge and sending a flow via that back edge contradicts with our assumption that the path from A to B is one-way. Am I missing something? Or there is a better intuitive way to understand this?

$\endgroup$
  • 2
    $\begingroup$ Ford-Fulkerson is described in detail in many textbooks... and you can work through examples yourself to help you get a better understanding as well. You're missing that the residual graph has edges with a different direction than the original graph. Many textbooks present an example illustrating why this is necessary (why F-F would get stuck without it), which may help give you intuition. Rather than us repeating that standard explanation, it'd make more sense for you to spend more time studying standard resources and see if you have a specific question after that. $\endgroup$ – D.W. Nov 26 '15 at 7:54
  • 3
    $\begingroup$ Actually, I have not been able to find a good explanation of this in my textbook and it would have been helpful if there was an answer to this question on CS.SE. Your comment does not answer the question nor does it point in any helpful direction. $\endgroup$ – dramzy Dec 12 '15 at 3:53

Your Answer

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

Browse other questions tagged or ask your own question.