鉴于网络流程发现如果有一个min切割，则只有一个给定的边缘铺设了它

Question

给定网络流 $ g=（v，e）$ 带有容量函数 $ c $ source $ s $ 和hole $ t $ ， 给定2边缘 $ e_1，e_2 $ 。

找到是否存在敏切，使得只有一个边缘属于min-cut。

希望得到帮助。

Answer 1

首先，计算网络的最小截止值 $ c $ 。

秒，删除边缘 $ e_1 $ 增加 $ e_2 $ 到无限远的容量计算新网络的最小截止值 $ c_1 $ 。

第三，删除边缘 $ e_2 $ 增加 $ e_1 $ 到无限远的容量计算新网络的最小截止值 $ c_2 $

现在您可以检查 $ c-c_1 \ ge c（e_1）$ 或 $ c-c_2 \ gec（e_2）$ 查看是否存在初始网络中的最小剪切，该初始网络包含 $ e_1，e_2 $ 。