0
$\begingroup$

Picture of network

I am trying to find the minimum cut of this flow network, but I feel like I have the cut wrong. Based off this post, I should try to find all reachable vertices in the residual network once there are no augmenting paths, and set that to partition "A", but then I get this weird cut. Is this the right cut?

$\endgroup$
2
  • $\begingroup$ Yes this is the right. Just compare the max flow with cut capacity. They must be the same by min-cut max flow theorem. Here cut capacity = max flow = 5. $\endgroup$ Commented Dec 12, 2020 at 13:03
  • $\begingroup$ Also, note an important property of a min cut that any edge that goes from $B$ to $A$ must have a 0 flow in the original graph. Here $B = V \setminus A$ $\endgroup$ Commented Dec 12, 2020 at 13:21

0

Your Answer

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

Browse other questions tagged or ask your own question.