Fulkerson最大流量算法分析

Question

我正在阅读由Robert编写的书算法中的算法。此处所述作者如下：

对于具有V顶点和E边的流网络，Fulkerson最大流算法的最短路径实现所需的增强路径数最多为EV /2。 证明草图:每条增强路径都有一条关键边缘--一条从残差网络中删除的边缘，因为它要么对应于一个正向边缘，而后者变成了容量，要么一个向后边被空了。每一条边是一个临界边时，通过它的增强路径的长度必须增加2。由于一条增强路径的长度最多为V/2，因此每个边最多可以在V/2增强路径上，并且增强路径的总数最多为EV/2。

我对上述案文的问题如下：

1. 如果预言路径长度在V上，那么每条边都可以位于V/2的最前兆路径中，这是怎么得到的？

如果可能的话，请用简单的例子解释上面的内容。

Answer 1

你首先需要证明之前的陈述

每一条边缘是一个关键的边缘，通过它的增强路径的长度必须增加2。

路径长度最多是V，因为两次遍历顶点是没有意义的(删除顶点x在这种路径上出现的两个顶点之间的所有边，那么您仍然有一条好的路径，至少有原始路径的容量)。

因此，如果路径长度最多为V，并且每一条边是临界的，则路径的长度增加2，那么边最多可以是V/2次。