最大流量 - 检测是否在某些最小切割中找到给定边缘

Question

给定网络G =(V,E),E中的最大流量f和边缘e,我需要找到一个效果算法,以便检测是否存在包含e的一些最小切割.另一个问题是,如果我发现e包含在某些最小切口中,是否可以检测到它是否是切割中最轻的边缘？

我已经考虑过运行Ford-Fulkerson算法,以及增加/减少给定边缘的容量并看看会发生什么,但我还没有提出可能有助于我解决问题的东西.

如果有人能指出我的解决方案,我会很高兴,在此先感谢.

Answer 1

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