探讨如何唯一确定最小割集的方法
最编程
2024-07-31 20:28:36
...
好吧，既然你现在不想要完整的答案，我会给你一些提示。尽可能多地阅读对你来说是必要的东西，如果你放弃了--去读吧，把它们全部读出来。
1:
剪裁是唯一的当且仅当没有其他的分切。
2:
如果你成功地找到了一个不同的分切，那么第一个分切并不是唯一的.
3:
你的链接给了我们一个分钟的切分，这是残差图中s的所有可达顶点。你能想出一种方法来获得不同的裁剪，而不一定是一样的？
4:
为什么我们要取特别是从s中可以到达的顶点？
5:
也许我们可以做些类似的事情？
6:
看同样的残差图，从t开始。看看从t到箭头的相反方向的顶点组(意思是所有可以到达t的顶点)。
7:
这个组也是一个极小的部分(确切地说是S\那个组)。
8 (最终答案)：
如果那个切割和你原来的相同，那就只有一个。否则，你只找到两个切割，所以原来的不可能是唯一的。