algorithm - Ford-Fulkerson最大流算法分析

Question

我正在阅读 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.

我对以上文字的问题是

1. 如果增广路径长度至多为 V，那么每条边最多可以有 V/2 个增广路径，我们是如何得出这一结论的？

请尽可能用简单的例子来解释上面的内容。

Answer 1

你首先需要证明前面的命题

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 次。