给定网络是否具有独特的最小切割？

Question

设G =(V,E)是一个网络,其中s和t是源和接收器.设f为G中的最大流量.找到一个算法,确定G中是否存在唯一的最小割数.

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

确定最小切割的唯一性

在那里给出答案的摘要:

找到残差图中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

=>:
您将边缘容量增​​加e1,计算新的最大流量并保持不变,这意味着e不在新的最小切割中.(如果e是,根据min-cut的属性,f(e)= e的容量,这导致增加).由于e不在新的最小切割中,它也是原始图形的最小切割,其与我们所知的切割具有相同的体积.因此,原始切割不是唯一的.

<=:
原始剪切不是唯一的(让我们称之为E和E'),这意味着你可以找到一个e在E但不在其中的边E'.然后你只需将容量增加e1.当计算新图的最小切割时,E'已经存在.由于E'不包含边缘e,因此毫无疑问,最大流量保持不变.

希望你能理解 :)