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$ Dec 12 '20 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$ Dec 12 '20 at 13:21

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.