1

我正在阅读 Robert Sedgewick 编写的 Algorithms 一书中的 Ford-Fulkerson maxflow 算法。这里作者提到如下

对于具有 V 个顶点和 E 个边的流网络，Ford-Fulkerson maxflow 算法的最短增广路径实现所需的增广路径数最多为 EV /2。

证明草图：每条增广路径都有一条关键边——一条从残差网络中删除的边，因为它对应于一条被填充到容量的前向边或一条被清空的后向边。每当一条边是关键边时，通过它的增广路径的长度必须增加 2。由于增广路径的长度最多为 V，因此每条边最多可以在 V/2 增广路径上，并且总增广路径最多为 EV/2。

我对上述文字的问题是

  1. 我们如何说如果增广路径长度最多为 V，则每条边最多可以在 V/2 增广路径中？

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

4

1 回答 1

1

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

每次边是临界边时，通过它的增广路径的长度必须增加 2。

路径长度最多为 V，因为通过顶点两次是没有意义的（删除这样的路径上两次出现的顶点 x 之间的所有边，你仍然会有一条好的路径，至少有容量原始路径的路径）。

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

于 2016-04-29T10:11:52.160 回答