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
I was playing around with https://visualgo.net/en/maxflow when I realized a pattern:
Take this graph, for example. We notice that the min-cut divides the graph into two sets of nodes: {0, 2, 3, 6} and {1, 4, 5, 7}.
I noticed that choosing any node within {0, 2, 3, 6} as a source and {1, 4, 5, 7} as a sink, or vice versa, produces the same min-cut edges.
Is this true in general? As in, will the min-cut produced be the same for any source-sink pair from one-side of a min cut to the other?
That is an interesting observation.
However, the propostion is not true in general. For a counterexample, consider the flow network with capacities $c(\overrightarrow{AB})=2$, $c(\overrightarrow{BC})=1$ and $c(\overrightarrow{AC})=1$.
Let $A$ be the source and $C$ be the sink. The unique min-$A$-$C$-cut is $(\{A,B\}, \{C\})$.
Let $B$ be the source and $C$ be the sink. The unique min-$B$-$C$-cut is $(\{B\}, \{A,C\})$.
