Given the following undirected graph, how would I find the max-flow/min-cut?
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.
By the way, for those who are curious, I'm using PDF Annotator 4 and a Wacom Intuos tablet to draw my graphs.