最大流 - 检测给定边是否在某个最小割中被找到

Question

给定一个网络G=(V,E)，一个最大流f和边缘e在E中，我需要找到一个有效的算法来检测是否存在一些包含e的最小割。 另一个问题是，如果我发现e包含在某个最小割中，是否有可能检测出它是跨越割的最轻的边？

我考虑过实施Ford-Fulkerson算法，增加/减少给定边缘的容量并观察结果，但我还没有想出一个能帮助我解决问题的方法。

如果有人能指点我找到解决方案，我将不胜感激。提前致谢。

- user975343

---

我不知道你第一个问题的答案，但是关于你的第二个问题：它并没有完全指定，因为 e 可能出现在两个不同的切割中，在其中一个中是最小权重，但在另一个中却不是。 - j_random_hacker

那我重新表达我的问题：是否有可能检测出它是否是任何最小割中的最轻重量？ - user975343

你不应该在多个网站同时发布同一篇文章。你应该选择最合适的网站，只在那里发布它。 - Bernhard Barker

Answer 1

这里是第一个问题的解决方案：假设w(e)是e的权重，计算G的最小割值，假设为C。然后我们从G中删除e以创建G'；再次计算G'的最小割值，假设为C'，如果C-C'>=w(e)，则可以得出结论：e参与了至少一个最小割（你已经知道它），否则e不属于任何最小割。

- Saeed Amiri

---

谢谢您的回答，但是“参与至少一个最小割（您已经知道它）”是什么意思？我已经知道什么了？如何知道的？ - user975343

@Itamar，如果C-C'>=w（e），意味着e参与了某个割。但是你知道至少有一个这样的割，因为C'+e具有这种属性。 - Saeed Amiri

谢谢，我还有一些问题 - 为什么是 C-C'>=w(e)，而不是 C - C' > w(e)？我怎么知道从 C-C'>=w(e) 中 e 参与了某个割？这个割是最小的吗？再次感谢。 - user975343

假设e是所有边中最小权重的桥，那么会发生什么？ - Saeed Amiri

如果你能解释一下你的意思，我会非常感激。 - user975343

你知道什么是桥吗？如果是的话，假设你的图是单位权重的，e是一座桥，那么e至少会形成一个最小割，因此C-C' = w(e) = 1。 - Saeed Amiri