I'm trying to find max-flow of such flow network: enter image description here

It seems to be 5, but how to prove it using the min-cut? I can't see any min-cut, which have a value of 5. I also heard in one video, that in min-cut one should count only edges, that goes from S to T, and other should be skipped, but this explanation is too vague. What is a proper way to find a min-cut?

  • $\begingroup$ I don't think there is a min-cut with value 5 in this graph. Every two nodes with an edge that has value more than 5 has to be on the same "side" in the min-cut, and its not hard to find such a sequence of nodes that reaches the target and starts from the source $\endgroup$
    – nir shahar
    Aug 6 '21 at 12:35

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.