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?

$\endgroup$
  • $\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 '18 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 '18 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$ – Apass.Jack Dec 13 '18 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 '18 at 20:41
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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