我正在寻找一个好的解决方案来在无向和未加权图中找到 s-t 最小切割边。我想使用推送重新标记算法。
但我不确定如何实现它以在无向和未加权图上找到最小割。
在每对顶点之间有两条反向边，并在所有边上赋予相同的权重，并应用推送重新标记算法？
我可以用这种方式得到最小切割吗？
我在下图上尝试过。顶点上的 a(m,n) 意味着 e(a)=m,h(a)=n。每条边的容量设置为1。
显然，最小切割是边缘（c，t）。但从最后一张图片中，我怎么知道（c，t）是最小切割边缘？或者我计算方法错误了。
有人能在这里指出我的错误吗？
欢迎建议，谢谢！
找到节点高度之间的间隙，然后通过帽找到最小切割边缘的边缘。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
