一尘不染

确定最小切割的唯一性

algorithm

免责声明:这 一个作业问题。截止日期已经过去,因此讨论可以继续进行而不必担心。

我挣扎的问题是,以确定特定的最小值是否 ST 切的曲线图 G =(V,E) 是唯一的。这是很简单的找到 一些
使用最大流算法为每分钟切这个例子,但你会如何表现它
最小割?


阅读 661

收藏
2020-07-28

共1个答案

一尘不染

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

1:
切割是唯一的,前提是没有其他最小切割。

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

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

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

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

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

7:
该组也是最小切割(确切地说,实际上是S \该组)。

8(最终答案):
如果该切割与您的原始切割相同,则只有一个。否则,您仅会发现2个切口,因此原始切口不可能是唯一的。

2020-07-28