为无向无权图实现推重贴标签算法s-t最小割边 [英] implement push relabel algorithm s-t min-cut edges for undirected unweighted graph

问题描述

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

I am looking for a good solution to find s-t min-cut edges in undirected and unweighted graph. I want to use push-relabel algorithm.

但是我不确定如何实现它以在无向和无权图上找到最小割。
在每对顶点之间有两个反向的边，并且在所有边上赋予相同的权重，并应用push-relabel算法？
是否可以通过这种方式进行最小切割？

But I am not sure how to implement it to find min-cut on undirected and unweighted graph. Having two edges in reverse between each pair of vertices and given same weight on all edges, and apply the push-relabel algorithm ? can I get min-cut in that way?

我在下图上进行了尝试。顶点上的a（m，n）表示e（a）= m，h（a）= n。并将每个边缘容量设置为1。

I tried it on the following graph. a(m,n) on vertex means e(a)=m,h(a)=n. and every edge capacity is set as 1.

显然，最小割是边（c，t）。但是从最后一张照片中，我怎么知道最小切边（c，t）？还是我用错误的方式计算了。

clearly the min-cut is the edge (c,t). but from the last pic, how can I know (c,t) is the min-cut edges? or did I computed in wrong way.

有人可以在这里指出我的错误吗？
欢迎提出建议，谢谢！

Could anyone point out my mistake here? Advises are welcomed, thanks!

推荐答案

找到节点高度之间的间隙，然后通过上限找到边缘最小切边。

find gap between heights of nodes, then by the cap find edges which are min-cut edges.

这篇关于为无向无权图实现推重贴标签算法s-t最小割边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！