0
$\begingroup$

So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value?

A) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

Suppose we were using 100 or maybe 75 instead of 50. Is this still true?

B) Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --> t paths in the residual graph Gf.

If we use 80, 60, 20 and so on is this still true? What about for odd numbers?

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm not sure I understand the question. What is the significance of the numbers you chose? The maximum flow value is always equal to the minimum cut value, regardless of what that value is. $\endgroup$
    – Zach Langley
    Dec 13, 2018 at 19:29
  • $\begingroup$ Ah, each of these were given to me as true/ false questions. I know that the initial statements are true, but I wanted to know if it was true if we changed the values. It sounds like A is always true for some flow f in a graph G, the capacity of the minimum cut is always the same as said flow for B) I know it's a true statement but does it remain true if we change the flow value (And also the cut capacity?) $\endgroup$
    – User9123
    Dec 13, 2018 at 19:47
  • $\begingroup$ Also posted five hours earlier on Stack Overflow. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration. $\endgroup$
    – John L.
    Dec 13, 2018 at 20:32
  • $\begingroup$ I'm sorry about that! Didn't realize. I realized that the question would be more appropriate for this community, which is why. I deleted the old one (is that okay?) $\endgroup$
    – User9123
    Dec 13, 2018 at 20:41

1 Answer 1

Reset to default
0
$\begingroup$

The value of any $st$-flow is at most the value of any $st$-cut, and they are equal if and only if the flow value is maximized and the cut value is minimized. Thus, statement (A) is false since $f$ isn't necessarily a maximum flow (since you claim (A) is true, maybe you forgot to mention that $f$ is a maximum flow, or you meant to say that the value of the cut is at least 50?). Statement (B) is true, since if there is a flow and cut of equal value, then the flow is a maximum flow and the residual graph has no path from $s$ to $t$.

Of course, the actual values don't matter. Only the relationship between the flow value and cut value is relevant.

Improve this answer
$\endgroup$

Your Answer

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

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