确定最小切割的唯一性

截止日期已经过去，因此讨论可以继续进行而不必担心。

我挣扎的问题是，以确定特定的最小值是否 ST 切的曲线图 G =（V，E） 是唯一的。这是很简单的找到一些

使用最大流算法为每分钟切这个例子，但你会如何表现它

的最小割？

好的，因为您不希望马上得到完整的答案，所以我会给您一些提示。尽可能多地阅读对您有必要的内容，如果您放弃，请继续阅读所有内容。

切割是唯一的，前提是没有其他最小切割。

如果成功找到其他的最小切割，则第一个最小切割不是唯一的。

您的链接给了我们一个最小割，这是残差图中s的所有可达顶点。您能想到一种获得不同切割（不一定相同）的方法吗？

为什么我们特别考虑到s可达的那些顶点？

也许我们可以做一些与t类似的事情？

查看相同的残差图，从t开始。在箭头的相反方向上查看从t可到达的一组顶点（意味着可以到达t的所有顶点）。

该组也是最小切割（确切地说，实际上是S \该组）。

如果该切割与您的原始切割相同，则只有一个。否则，您仅会发现2个切口，因此原始切口不可能是唯一的。