Given the following undirected graph, how would I find the max-flow/min-cut?

Original graph

Now, I know that in order to solve this, I need to redraw the graph so that it is directed as shown below. However, after this, I'm stuck. I chose the olive-colored path from a -> z to begin the algorithm. However, I'm not sure what to do with the complementary edges going from z <- a. I remember hearing somewhere that I should increase the capacity on these edges by the amount of flow sent through along the a -> z path. I guess that makes somewhat intuitive sense because now I have more flow that can be sent back, but I'd like to be 100% sure.

enter image description here

By the way, for those who are curious, I'm using PDF Annotator 4 and a Wacom Intuos tablet to draw my graphs.


1 Answer 1


Yes, you should increase the capacity of reverse edge by flow sent. Each time sending some flow by edge you should update its reverse edge too, so that flow passes only in one direction and the reverse edge has capacity = initial capacity + flow.

https://stackoverflow.com/questions/7687732/maximum-flow-ford-fulkerson-undirected-graph http://www.inf.ufpr.br/pos/techreport/RT_DINF003_2004.pdf


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .