免责声明:这 是 一个作业问题。截止日期已经过去,因此讨论可以继续进行而不必担心。
我挣扎的问题是,以确定特定的最小值是否 ST 切的曲线图 G =(V,E) 是唯一的。这是很简单的找到 一些 使用最大流算法为每分钟切这个例子,但你会如何表现它 的 最小割?
好的,因为您不希望马上得到完整的答案,所以我会给您一些提示。尽可能多地阅读对您有必要的内容,如果您放弃,请继续阅读所有内容。
1: 切割是唯一的,前提是没有其他最小切割。
2: 如果成功找到其他的最小切割,则第一个最小切割不是唯一的。
3: 您的链接给了我们一个最小割,这是残差图中s的所有可达顶点。您能想到一种获得不同切割(不一定相同)的方法吗?
4: 为什么我们特别考虑到s可达的那些顶点?
5: 也许我们可以做一些与t类似的事情?
6: 查看相同的残差图,从t开始。在箭头的 相反 方向上查看从t可到达的一组顶点(意味着可以到达t的所有顶点)。
7: 该组也是最小切割(确切地说,实际上是S \该组)。
8(最终答案): 如果该切割与您的原始切割相同,则只有一个。否则,您仅会发现2个切口,因此原始切口不可能是唯一的。