如何使用最大流量算法在图表上找到最小割数？
ces*_*rbs 56 cut flow graph-theory minimum max-flow
我需要在图表上找到最小切割.我一直在阅读关于流网络的内容,但我能找到的是最大流算法,如Ford-Fulkerson,push-relabel等.鉴于最大流量最小切割定理,是否可以使用其中一种算法来查找使用最大流算法在图表上的最小割数？怎么样？
到目前为止我发现的最好的信息是,如果我发现"饱和"边缘,即流量等于容量的边缘,那些边缘对应于最小切割.真的吗？这对我来说听起来不是100%.确实,最小切口上的所有边缘都将饱和,但我相信也可能存在饱和边缘,这些边缘超出最小切割"路径".
Fal*_*ner 46
从源顶点开始,沿着剩余网络中的边缘进行深度优先搜索(即,具有流的边缘的非饱和边缘和后边缘),并标记可以通过这种方式到达的所有顶点.切割包括从标记顶点到未标记顶点的所有边.显然,这些边缘是饱和的,因此没有遍历.如您所述,可能存在其他饱和边缘不属于最小切割的一部分.
- 这并不总是正确的,对于DAG来说会没问题.查看dingalapadum的答案 (5认同)
din*_*dum 27
我不想挑剔,但建议的解决方案并不像提议的那样正确.
正确的解决方案:您实际应该做的是Residual-Network Gf上的bfs/dfs (在维基百科上阅读)和标记顶点.然后你可以选择带有标记的从顶点和未标记到顶点的那些.
为什么'跟随不饱和边'是不够的:考虑一下,流算法使边缘饱和,如图所示.我用绿色标记了"正在跟随不饱和边缘"的方法我正在访问的顶点.显然,唯一正确的最小切割是来自EF的边缘,而建议的解决方案也将返回AD(甚至可能是DE).
请注意,如果我们考虑使用残差网络,dfs/bfs将访问顶点D,因为从E到D会有一条边,从而使边EF成为唯一一个带有标记的从顶点和未标记的边.到顶点.
- 你不挑剔!以上答案都是错误的.谢谢. (7认同)
- 对于那些正在努力弄清楚为什么在残差图中访问与仅跟随残差边不同的人：饱和边并不意味着路径被阻塞，因为可能存在来自相反方向的流量抵消。 (2认同)