我正在阅读 Robert Sedgewick 编写的《算法》一书中的 Ford-Fulkerson maxflow 算法。这里作者提到如下
The number of augmenting paths needed in the shortest-augmenting-path implementation of the Ford-Fulkerson maxflow algorithm for a flow network with V vertices and E edges is at most EV /2.
Proof sketch: Every augmenting path has a critical edge—an edge that is deleted from the residual network because it corresponds either to a forward edge that becomes filled to capacity or a backward edge that is emptied. Each time an edge is a critical edge, the length of the augmenting path through it must increase by 2. Since an augmenting path is of length at most V each edge can be on at most V/2 augmenting paths, and the total number of augmenting paths is at most EV/2.
我对以上文字的问题是
- 如果增广路径长度至多为 V,那么每条边最多可以有 V/2 个增广路径,我们是如何得出这一结论的?
请尽可能用简单的例子来解释上面的内容。
最佳答案
你首先需要证明前面的命题
Each time an edge is a critical edge, the length of the augmenting path through it must increase by 2.
路径长度最多为 V,因为两次通过一个顶点是没有意义的(删除在这样的路径上两次出现的顶点 x 之间的所有边,你仍然会有一个好的路径,容量至少是原始路径的容量)。
因此,如果路径长度至多为 V,并且每次一条边是临界的,路径的长度增加 2,那么一条边最多可以是临界的 V/2 次。
关于algorithm - Ford-Fulkerson最大流算法分析,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36932625/