0

我不确定我是否对 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,我目前正在使用“选择任意源,尝试所有其他节点”方法),它必须要求在两个方向上的流量相等任何边缘。

示例图

4

1 回答 1

1

"source=B, sink=A" 的“正确”最小切割为 0,因为没有边 B->A(等效地,c(B, A) = 0);看起来您的实现可能正在回答一个不同的问题。您是否检查了 BFS 阶段中每条潜在的最短路径以确保它在接收器处结束?

(意思是 mincut 是在询问“不允许 B 连接到 A 的最小值是多少”,而不是“将图形分成 2 个分区的最小值是多少)。

是的,第一个:我们只关心从源到汇的瓶颈(max-flow min-cut theorem)。Min-cut确实将图“划分”为两部分,但还有一个额外的要求,即源和汇在不同的集合中。

(一般的最小切割,我目前正在使用“选择任意来源,尝试所有其他节点”方法)

如果您说“将所有其他节点视为汇”,这是对源外边缘的简单度数计算。

编辑:由于边缘是加权的,因此它不完全是度数计算,但它只是将边缘权重相加,无需搜索。

它必须要求在任何边缘的两个方向上都有相等的流量。

不存在这样的要求(流网络是有向图 - 任何无向边都映射到两条反平行边,对于特定的流问题,只使用一条边)。

于 2016-05-20T03:23:02.060 回答