实施推送重贴算法 S-T 最小割边用于无向无权图

Question

3

我正在寻找一种好的解决方案，以在无向且无权图中找到s-t最小割边。我想使用推送-重贴标签算法。

但是我不确定如何将其实现以在无向且无权图中找到最小割。对于每对顶点之间都有两个相反的边，并给所有边相同的权重，然后应用推送-重贴标签算法吗？这样可以得到最小割吗？

我在下面的图上尝试了它。在顶点上的a(m,n)表示e(a)=m，h(a)=n。每条边的容量都设置为1。

很明显，最小割是边缘(c,t)。但从最后一张图片中，我怎么知道(c,t)是最小割边缘？还是我计算错误了。有人能指出我的错误吗？欢迎提供建议，谢谢！

- arslan

是的，那样可以。 - HenryLee

@HenryLee，我更新了问题并添加了一个示例，你能看一下吗？我认为我在某个地方出错了。 - arslan

1

标签1、2、3、4是空缺的，因为在算法结束时没有带有这些标签的顶点。其中任何一个都代表着相同的最小割，即S = {s，a，b，c}和T = {t}。原图中从S到T的所有边都是割边，在这种情况下只有边（c，t）是割边。 - Niklas B.

1

要实现一个良好的推送-重贴标签算法，请查看http://www.avglab.com/andrew/soft.html中的HI-PR和F_PRF。 - Niklas B.

@HenryLee。是的，我理解两个节点之间的两条边对于Ford-Fulkerson算法很重要。我认为Niklas B的解释适用于这个推送-重贴标签算法。谢谢 :) - arslan

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- arslan · Accepted Answer

找到节点高度之间的差距，然后通过容量找到最小割边。