2
$\begingroup$

I was playing around with https://visualgo.net/en/maxflow when I realized a pattern:

enter image description here

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

a simple flow network made with
https://graphonline.ru/

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.