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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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.