7

假设我在图 G = (V,E) 上运行了 Ford-Fulkerson 算法，结果是一个 max-flow f max，它与一个 min-cut Xmin 相关联。我有兴趣通过增加图中任何一条边的容量来尽可能地增加流量。我怎样才能识别这个边缘？

一种策略可能是：给定初始顶点s和最终顶点t ，考虑从s到t的所有路径并验证容量较低的边。例如，如果我有一个 1/1 的边，这是我必须增加容量的顶点。

有解决这个问题的通用算法吗？

4

1 回答 1

8

一旦你在图中找到了最大流量，增加边 (u, v) 的容量只会增加最大流量，前提是在残差图中存在从 s 到 u 和从 v 到 t 的正容量路径。如果不是这种情况，那么在增加之后，残差图中就不会有增广路径，因此最大流量将保持最大。

在具有此属性的边 (u, v) 中，在增加 (u, v) 的容量后，您可以从 s 推送到 t 的最大额外流量将是有界的。如果你可以推动任何流穿过这条边，你必须通过找到从 s 到 u 的路径和从 v 到 t 的路径来做到这一点。这样做时，两条路径中的每一条都会有一个瓶颈边缘，并且流量不能增加超过这个。因此，解决该问题的一种选择是执行以下操作：

  • 在残差图中找到从 s 到可从 s 到达的每个其他节点的最大瓶颈路径。
  • 在残差图中找到从每个节点可以到达 t 到 t 的最大瓶颈路径。
  • 对于穿过路径的每条边 (u, v)，可以推动通过边的最大额外流量由从 s 到 u 的最大瓶颈路径和从 v 到 t 的最大瓶颈路径的最小值给出.

换句话说，如果您可以计算图中的最大瓶颈路径，您可以找到应该在时间 O(B(m, n) + m) 中增加的边，其中 B(m, n) 是计算图中的最大瓶颈路径。

幸运的是，这是一个经过充分研究的问题，可以使用 Dijkstra 算法的一种变体来解决，其中不是存储到每个节点的最小成本路径，而是存储到每个节点的最大瓶颈路径。一个快速的谷歌搜索应该会出现一些额外的信息。使用斐波那契堆，您可以在 O(m + n log n) 时间内实现此搜索，因此识别应增加容量的边的总运行时间也应为 O(m + n log n)。

希望这可以帮助！

于 2013-06-10T02:31:55.737 回答