3

我有以下两个问题。

  1. 对或错：我们总是可以在 Ford-Fulkerson 算法中找到一系列流增强 st 路径，这样我们就可以在多项式迭代中达到最大流。
  2. 对或错：我们总是可以在 Ford-Fulkerson 算法中找到一系列流增强 st 路径，这样我们只有在指数级迭代后才能达到最大流。
4

2 回答 2

1

第一个答案肯定是假的。因为 Ford-Fulkerson 算法的运行时间不是多项式的——它是指数的。

因此，为了找到所有 st 路径以达到最大流量将花费指数时间。

Ford-Fulkerson 算法的运行时间是O(nV)，更准确地说O((n+m)V)，其中n是节点数，m是图中的边数。并且V是图表具有的最大容量。

因此，它可能看起来像一个多项式时间算法。但是，如果V很大，让我们假设这个大数可以表示为2^k，那么运行时间就变成了O(n. 2^k)- 这是指数的。

第二个答案在某些情况下也不正确，但如果您正在考虑图中容量值的整数/有理数，则大多数情况下都是正确的。我们知道该算法需要指数级的时间——这没有问题。但是，如果图的容量值是不合理的，那么 Ford-Fulkerson 算法不保证终止。因此，第二个陈述也有些错误。然而，在大多数情况下，容量都是整数或有理值，因此在大多数情况下都是如此。

于 2019-03-13T20:55:32.653 回答
0

第一个说法是正确的。第二个说法是错误的。

G_f 表示 G 残差网络，c_f 是 G_f 中的容量。据我所知，这是福特富尔克森方法：

1) Define: f(u,v) = 0, for all (u,v) in E.

2) while there exits a path p from s to t, in G_f:

    3)     c_f(p) = min{c_f(e) : for all e in p}

    4)     for (u,v) in p:

        5)         if (u,v) in E:

            6)             f(u,v) += c_f(p)

        7)         else:

            8)             f(u,v) -= c_f(p)

到过程结束时，f 是最大流量。（您可以阅读 CLRS 的“算法简介”中的证明）

该算法的运行时间是 O(X(V+E))，X 是 while 循环迭代的次数。

现在 - 我们可以使用 BFS 搜索在第 (2) 行找到 p。这种方法确保我们迭代 while 循环 O(VE) 次。此实现也称为 Edmonds-Karp 算法。因此，总运行时间为：O(VE*(E+V))。

这应该回答您的第一个问题 - 我们总是可以通过在多项式时间内增加路径 st 来找到最大流量。

关于第二个问题：考虑一个图 G，其中所有容量的值为 1。显然，最大流量值小于 |E|。

由于 while 循环的每次迭代都会将流 f 的当前值增加一个正整数（实际上是 1。如果您需要证明，请转到 CLRS），我们有 while 循环最多迭代 |E| 次。因此，无论我们如何选择增广路径，我们的运行时间都是 O(E*(E+V)。该图与第二个主张相矛盾。

于 2019-10-29T08:41:00.697 回答