Yesterday I found a question here, that asked, if the value of the flow across the edges of the MinCut is at capacity.

I think the question has been deleted.

But I want to confirm that for the edges that are on the MinCut, after the MaxFlow is found, their flow values will either be zero or equal to their full capacities. Is it correct or not ?

  • 1
    $\begingroup$ What are your thoughts? Have you tried working through some examples? Have you spotted a pattern? Have you tried to prove the pattern or look for a counterexample? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 28 '18 at 18:50
  • $\begingroup$ @D.W. according to me at the mincut, for the the two sets A and B, A has the nodes (in the residual graph) reachable from s and other nodes end up in B. Since, nodes of B in residual graph are not reachable from s, there should not be a backward edge to the nodes in B , which is possible if the flow through the edge is at full capacity or the edge is in reverse direction in G, where the flow through such an edge should be zero. So I believe the answer is correct. P.S. this is not a homework question :P $\endgroup$ – S K Mar 28 '18 at 19:46
  • 1
    $\begingroup$ Please don't respond in the comments. Instead, think about the problem for a while, then revise your question using the 'edit' link, based on the feedback you've received. If you believe your answer is correct, your next step should be to try to prove it, then edit to ask about some specific aspect you got stuck on. Make sure the revised question reads well for someone who encounters for the first time. Don't just append stuff at the end of your question, but write it so it reads well and is coherent. We want high-quality questions that are likely to be useful to others in the future. $\endgroup$ – D.W. Mar 28 '18 at 20:47
  • 1
    $\begingroup$ I suggest that you spend some time reading the proof of the max-flow min-cut theorem and make sure you understand that proof. That's explained in many standard resources, and once you understand it, you should be in a better position to answer your own question. $\endgroup$ – D.W. Mar 28 '18 at 20:49

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.