2
$\begingroup$

The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements in the graph does not matter.

However, if this is the correct notion of partitioning, then can construct a pathological example. Consider the following network. $$s \to B_1 \to A_1 \to B_2 \to A_2 \to t.$$Let each of the edges have a capacity of $1$. Then the max flow is clearly $1$. If we let the $s$-$t$ cut be such that set $A$ consists of $s$, $A_1$ and $A_2$, and $B$ is the rest, then the capacity of the cut is $3$ since there is a flow of value $1$ exiting each of the $3$ vertices in $A$. This contradicts the max-flow-min-cut theorem.

Is my understanding right then that the $s$-$t$ cut is not a partition of a set but a graph? By this I mean, that the resultant two sets have to be contiguous?

$\endgroup$
  • $\begingroup$ What do you mean by "the positioning of elements in the graph does not matter"? $\endgroup$ – David Richerby Dec 31 '14 at 12:55
4
$\begingroup$

The example is correct: in this $s$-$t$ cut the capacity of the cut is indeed $3$. However, the min-cut in the max-flow min-cut theorem talks about the capacity of the minimum $s$-$t$ cut. So one must take an $s$-$t$ cut that gives minimum capacity: what you have in your example is not one of them.

$\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.