2
$\begingroup$

I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking something simple, but I've been staring at this for 10 minutes now... Can anyone explain what Im missing? did the image work?

$\endgroup$

1 Answer 1

1
$\begingroup$

The edge from $2$ to $3$ isn't part of the minimum cut. It's oriented in the wrong direction, from the sink side to the source side, so you can delete it from your cut and there's still no path from $s$ to $t$.

$\endgroup$
1
  • $\begingroup$ Thank you! I didn't notice the opposite direction. $\endgroup$
    – Zouter
    Jan 22, 2017 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.