Ford-Fulkerson最大流算法分析

我正在阅读由Robert Sedgewick编写的书算法中的Ford-Fulkerson maxflow算法。这里作者提到如下Ford-Fulkerson最大流算法分析

Ë边缘在最短增强路径实施福特 - 富尔克森maxflow算法的所需的流动网络采用V顶点增广路径和的数量最多为EV/2 。

证明草图：每个增强路径具有从剩余网络，因为它对应要么变得满额或被排空后向边缘前边缘删除的临界边缘的边缘。每当边缘是临界边缘时，穿过它的增大路径的长度必须增加2.由于增加路径的长度最多为V，所以每条边可以至多增加V/2路径，并且路径增加路径的总数最多为EV/2。

我上面的文字问题是

我们是如何走到说如果augumenting路径长度为atmost V，每一个边缘可以在atmost V/2 augumenting路径？

要求用简单的例子来解释上面的例子，如果可能的话。

来源

2016-04-29 venkysmarty

这对于计算机科学SE更适合吗？ –

首先需要证明前面的语句

每一次的边缘是一个重要的优势，增广路径的长度，通过它必须由2

增加的路径长度最多为V，因为穿过顶点两次是没有意义的（在这样的路径上移除顶点x的两个出现点之间的所有边，并且您仍然有一条良好的路径，其容量至少是原始的路径）。因此，如果路径长度至多为V，并且每当边缘为临界时，路径的长度增加2，则边缘可以是至多V/2次的关键。

来源

2016-04-29 10:11:52 Sorin

感谢您的解释。对不起，我没有安静下来。你的意思是“删除这样一条路径上两个顶点x之间的所有边”。？ – venkysmarty

如果你有一个路径'source，a，B，c，d，e，f，g，B，sink'，那么你可以通过消除'B'到'得到'源，a，B，汇'。新路径总是到达相同的目的地，并且其容量至少与原始较长路径一样大。基本上说它是两次通过一个顶点没有意义。 – Sorin

OP应该标记为正确的，这是一个很好的答案！ – darkhipo

Ford-Fulkerson最大流算法分析

回答

相关问题