The definition of an s-t cut is a partition of the set of vertices V into 2 sets

Question

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?B1?A1?B2?A2?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, A1 and A2, 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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.