dav*_*vin 22
大纲:
给定最小ST切割,(U,V)具有切边E',我们做一个简单的观察:如果这个最小切割不是唯一的,那么存在一些具有一组切边E''的其他最小切割,这样E''!= E'.
如果是这样,我们可以遍历E'中的每个边,添加到其容量,重新计算最大流量,并检查它是否增加.
作为上述观察的结果,在E'中存在边缘,当增加时,如果原始切割不是唯一的,则最大流量不会增加.
我会让你填写细节并证明这是一项多时间任务.
Era*_*man 13
好的,既然你不想马上得到整个答案,我会给你一些提示.尽可能多地阅读您认为必要的内容,如果您放弃 - 请继续阅读所有内容.
1:
如果没有其他最小切割,则切割是唯一的.
2:
如果你成功找到了不同的最小切割,那么第一次切割并不是唯一的.
3:
你的链接给了我们一个min-cut,它是残差图中s的所有可到达顶点.你能想到一种获得不同切割的方法,不一定相同吗？
4:
为什么我们特别从s可以获得那些顶点？
5:
也许我们可以做一些与t类似的事情？
6:
从t开始,查看相同的残差图.查看箭头反方向可从t到达的顶点组(意味着可以到达t的所有顶点).
7:
这个组也是最小切割(或者实际上是S \,确切地说是那个组).
8(最终答案):
如果切割与原始切割相同,那么只有一个.否则,您刚刚发现了2个切口,因此原始切割不可能是唯一的.