graph-algorithm - 给定的网络是否有唯一的 Min-Cut？

Question

设 G = (V, E) 是一个网络，其中 s 和 t 是源和汇。设 f 是 G 中的最大流。找到一个算法来确定 G 中是否存在唯一的最小割。

我设法在这个网站上找到了一个类似的问题:

Determining the uniqueness of a min-cut

那里给出的答案摘要:

在残差图中找到从 s 可到达的所有顶点，我们在 G 中找到了一个最小割 (S,T)。

查看相同的残差图，从 t 开始。以箭头的相反方向查看从 t 可到达的顶点组(即可以到达 t 的所有顶点)。

这组也是一个最小的剪辑。

如果该剪辑与您的原始剪辑相同，则只有一个。否则，您只会找到 2 个剪辑，因此原始剪辑不可能是唯一的。

我不明白为什么如果剪辑与原始剪辑相同，那么剪辑就是独一无二的。
谁能向我们保证没有其他最小剪辑？

提前致谢

Answer 1

其实，我不太明白那个解决方案。但是在最初的问题中，davin 提供的第二个答案是绝对正确的。

我只是复制并粘贴到这里

Given a minimum S-T cut, (U,V) with cut-edges E', we make one simple observation:
If this minimum cut is not unique, then there exists some other minimum cut with 
a set of cut-edges E'', such that E'' != E'.

If so, we can iterate over each edge in E', add to its capacity, recalculate the
max flow, and check if it increased.

As a result of the observation above, there exists an edge in E' that when
increased, the max flow doesn't increase iff the original cut is not unique.

我自己的一些解释 :

你实际上需要证明的是

there exists an edge in E' that when increased, the max flow doesn't increase
<=>
the original cut is not unique

=>:
你增加edge的容量 e按1，计算新的最大流量，它保持不变，这意味着 e不在新的最小切割中。 (如果 e在，根据min-cut的性质，f(e)=e的容量，导致增加)。自 e不在新的最小割中，它也是原始图的最小割，与我们已知的割具有相同的体积。因此，原始割不是唯一的。

<=:
原始切割不是唯一的(我们称它们为 E 和 E' )，这意味着您可以找到一条边 e这是在 E但不在 E' .那么你只需增加 e的容量by 1. 在计算新图的最小割时， E'已经在那里了。自 E'不包含边 e , 毫无疑问，最大流量保持不变。

希望你能理解 :)