2
$\begingroup$

This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut theorem.

http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Example

$\endgroup$
1
$\begingroup$

Max flow isn't 9 it is 7. 4 from s to 1 and 3 from s to 2.It cannot have more than that.You can see that it is also equal to min-cut.

$\endgroup$
1
$\begingroup$

The flow depicted in the diagram has value 7. This is the total amount of flow out of the source node $s$, as well as the total amount of flow into the sink node $t$. Since the total capacity out of the source node $s$ is 7, this flow is maximum, i.e., no flow has larger value. This is also the value of the cut which separates $s$ from the rest of the graph. The existence of a flow of value 7 shows that this cut is minimum (if there was a cut of smaller value then there couldn't be a flow of value 7 since it could not cross the cut).

While the total capacity of edges incoming at $t$ is 9, no flow saturates these edges. Consider the thought experiment in which we changed the capacity of these edges to be infinite. Would you then say that the max flow is $\infty$?

That the max flow is at most the min cut is not hard to see: basically, each cut constrains each flow, and in particular the max flow is at most the min cut. The non-trivial part of the max flow min cut theorem is that the it is possible to achieve a flow whose value is the min cut, or conversely that there exists a cut whose value is the max flow.

$\endgroup$
0
$\begingroup$

Okay, really sorry. I got confused with maximal and max flow in the graph. Obviously, the maximal is what is at most the capacity, and max flow is how much at most can flow though this network. The answer to the former is of course 9, where at the latter is 7.

In this case the max flow from s to t through 1 is 4 and from s to t through 2 (as first node) is 3 which equals the min cut, which is the dashed arrow.

I hope this helps anyone who had the same confusion.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you mean. A "maximal" object is one that can't be added to; a "maximum" object is one that is bigger than all others. For example, vertex 1 is a maximal independent set in the graph in your question (you can't add another vertex and stil have an ind. set), whereas {s,t} is a maximum ind. set, since there is no ind. set with strictly more than two vertices. So I don't understand how you can claim that the maximal flow (9) is bigger than the maximum flow (7): that's impossible. $\endgroup$ – David Richerby May 4 '14 at 7:16
  • $\begingroup$ encase you miss understood at most you can push through 9 in this graph through t which is the capacity at t, the capacity at s is 7, which is the max that can be passed through the whole graph. $\endgroup$ – joker May 4 '14 at 7:43

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.