免责声明：这是一道已经过去的作业问题。现在已经过期，所以可以继续讨论而不必担心截止日期。
我正在努力解决的问题是确定图 G=（V，E） 中特定的最小 s-t 割是否唯一。使用最大流算法可以很容易地找到某些最小割，就像这个例子一样，但是如何证明它是最小割？
3个回答
27
概述：
给定最小S-T割（U，V）和割边E'，我们可以得到一个简单的观察结论：如果这个最小割不唯一，则存在另一个最小割，其割边集合为E''，且E''≠E'。
如果有这样的情况，我们可以遍历E'中的每条边，增加它的容量，重新计算最大流，并检查是否增加了。
由上述观察结果，存在一条边在增加时，当且仅当原始割不唯一时，最大流不会增加。
我将让您填写详细信息并证明这是一个多项式时间任务。
- davin
2
唉，其实很简单…… 我之前确实考虑过修改流量容量，但是放弃了那条路，因为它涉及在一个“不同”的图上解决最大流问题。 - Daniel Buckmaster
在这个链接中，他举了一个多个最小割的例子吗？https://stackoverflow.com/questions/34820333/are-there-more-than-one-families-of-flow-networks-with-non-unique-minimum-cuts?rq=1 - arkham knight
19
好的，既然您不想一下子得到整个答案，我会给您一些提示。请阅读您认为必要的提示，如果您放弃了 - 那么请继续阅读所有提示。
1:
当且仅当没有其他最小割时，该割是唯一的。
2:
如果您成功找到了另一个最小割，则第一个最小割就不是唯一的。
3:
您的链接给出了一个最小割，这是残留图中从 s 可达的所有顶点。您能想到一种获得不同割的方法吗？
4:
为什么我们特别选择了那些从 s 可达的顶点？
5:
也许我们可以从 t 中做类似的事情？
6:
在相同的残留图中，从 t 开始。看看所有可以到达 t 的顶点（即沿箭头反向的所有顶点）组成的顶点组。
7:
这个组也是一个最小割（或者确切地说是 S \ 该组）。
8 (最终答案):
如果该割与您的原始割相同，则只有一个割。否则，您刚刚找到了两个割，因此原始割不可能是唯一的。
- Eran Zimmerman Gonen
3
实际上，这也符合我画出的例子...（我确实看了整个内容...但感谢您对此进行了解释！）虽然它似乎比上面简单得多。这对我来说也是有道理的。您对 @davin 给出的答案有什么看法？ - Daniel Buckmaster
@DanielBuckmaster的回答也可以，但复杂度更高：如果我没记错的话，它是|E|*（|V|+|E|），而不仅仅是我的情况下的（|V|+|E|）。 - Eran Zimmerman Gonen
假设最大流已经计算出来了。我知道的所有最大流算法都在_O(|V|^3)_或等价的时间复杂度范围内。如果有一种快速(O(|V|))的方法可以在增量修改后重新计算最大流(我怀疑有...需要问我的导师)，那么另一种方法将降至相同的时间复杂度(尽管如果考虑常数，可能会更慢)。 - Daniel Buckmaster
3
考虑到最大流/最小割问题实际上是线性规划问题（分别为原始问题和对偶问题），我认为任何用于检查LP解唯一性并找到替代最优解的方法都可以应用于此背景下。
我通过谷歌找到了这篇文章：On the Uniqueness of Solutions to Linear Programs。
编辑1：基于dzhuang的建议，对于那些不知道最大流-最小割定理是线性规划中强对偶定理的特殊情况的人，请参考以下链接以了解这个细节：https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Linear_program_formulation。
- Jayant Apte
3
最大流问题是一个线性问题，但最小割问题不是。 - Jayant Apte
@Dzhuang，您认为最小割不是线性问题的哪个方面？ - Jayant Apte
抱歉，我的错，我没有注意到您提到了素数/双重关系。我撤回我的批评，如果您可以编辑（例如，添加上述维基百科参考资料）您的原始答案，那么我可以取消踩一下，并点赞。 - Dzhuang
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接