如何使用最大streamalgorithm在图上find最小切点?

我需要在图表上find最小切割。 我一直在读stream动networking,但是我能find的是最大streamalgorithm,例如Ford-Fulkerson,push-relabel等。给定最大stream最小割定理,是否可以使用其中一种algorithm来查找使用最大streamalgorithm在图上最小化切割? 怎么样?

到目前为止,我发现的最好的信息是,如果我发现“饱和”的边缘,即stream量等于容量的边缘,则这些边缘对应于最小切割。 真的吗? 这听起来并不完全正确。 确实,最小切割的所有边缘都是饱和的,但是我相信也可能存在饱和边缘,它们不在最小切割“path”之内。

从源顶点开始,沿残差networking的边缘进行深度优先search(即,具有stream动的边缘的非饱和边缘和后边缘),并标记可以以这种方式到达的所有顶点。 切割由从标记到未标记顶点的所有边组成。 显然,这些边缘是饱和的,因此没有被穿越。 如您所述,可能还有其他饱和边缘不属于最小切割的一部分。

我不想挑剔,但build议的解决scheme并不完全正确。

正确的解决scheme :你实际上应该做的是残余networkingGf上的bfs / dfs( 在维基百科上阅读它 )并标记顶点。 然后,你可以select标记从顶点到无顶点的标记。

为什么“遵循不饱和边缘”是不够的 :考虑到stream动algorithm饱和边缘,如图所示。 我用“绿色的不饱和边缘”方法标记了我正在访问的顶点。 显然唯一正确的最小切割是EF的边缘,而build议的解决scheme也会返回AD(甚至可能是DE)。

在这里输入图像说明 注意,如果我们考虑剩余networking,那么顶点D将被dfs / bfs访问,因为从E到D会有一个边缘,从而使边缘EF成为唯一一个带有标记的顶点和没有标记的边缘到顶点。

注意:Falk的algorythm可以用来find最小的顶点和顶点的最小切割。 对于后者,该algorithm应该颠倒,即。 search水槽顶点而不是源。 看到一个相关的问题: networkingstream量:添加一个新的边缘

要理解的一个方法是,让我们定义一个切割为两个集合S和T,它们分别包括s和t。

现在,将剩余networking中s中所有可以到达的S中的所有顶点相加,并将余下的边添加到T中。这将是一次剪切。

其次,可以通过将剩余networking中从t到达的T中的所有顶点置于其中,并将剩下的顶点置于S中来形成剪切。

看看这个video,找出我们如何find从s和t到达的顶点。

https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma

在计算最大stream量之后,我们可以search边(u,v) ,使得在残差图中从vu的残差图中有一个边,并且f(v,u) = c(u,v) [这意味着边缘饱和]

在筛选出这些边缘之后,我们可以使用这样的标准来select这样的边缘(u,v) ,即在残差图中不存在从u到sink的path。 如果满足这个条件,那么这样的边形成(S,T)切的一部分

该algorithm的运行时间可以是O(E) * O( V + E ) = O( E^2 )

我想这是其他人所说的,但是我发现它不清楚,所以这里是我的解释:

从源节点开始,对图进行洪泛填充,仅沿着具有剩余容量的边行进,标记每个访问顶点。 你可以使用这个DFS。 回想一下,从一个顶点的后沿有一个剩余能力 – 等于沿着前沿的stream量(即r(u,v)=边缘(u,v)的剩余能力,r(v,u)= flow(u ,v))。

实际上,这决定了图的ST裁剪的S部分。

现在最小的切割就是这样一组边,这样一个顶点从上面的填充区标记出来,另一个顶点没有标记。 这些将是没有剩余容量的边缘(否则,您将在您的DFS中遍历它们),并且一起形成最小割。

去除这些边缘之后,未标记的顶点集合将形成切割的T部分。

所以,要给出确切的程序如何获得最低限度的裁减:

  1. 运行Ford-Fulkersonalgorithmfind最大stream量并得到残差图1
  2. 在残差图上运行BFS以find残差图中可以从源访问的顶点集(考虑到您不能在残差图中使用容量为0的边)重要:必须在残差中使用反向边图find正确的可达顶点集!!! (见这个algorithm)
  3. 原始图中所有从可达顶点到不可达顶点的边都是最小切割边。 打印所有这些边缘。

1图中边缘的容量被定义为它的原始容量减去其stream量(来自最大stream量networking的stream量)。