我不确定我是否对 mincut 有误解,但我已经使用 edmond-karps 编写了一个 mincut 算法,然后是流网络上的 BFS。
如果我告诉它从 A 到 B 做一个 mincut,它会起作用,因为剩余流 A->B = 0,所以它产生集合 {A},切割为 A->B (1)。
但是,如果我告诉它从 B 到 A 做一个 mincut,它不会增加任何边(因为 C 没有边),所以结果集是 {C},有一个 B->丙(2)。
在我看来,我可能会以两种方式中的一种方式误解这一点。首先,从 B 到 A 的 mincut 可能是正确的,因为只计算 B 集合中的边,而不是边(意味着 mincut 是在询问“不允许 B 连接到 A 的最小值是多少”,而不是“将图形分成 2 个分区的最小值是多少)。
或者,如果您被要求在流网络上查找 mincut(一般的 min-cut,我目前正在使用“选择任意源,尝试所有其他节点”方法),它必须要求在两个方向上的流量相等任何边缘。