7

http://postimg.org/image/nfw50be6p/

如何在这个无向图中找到最大流量？任何人都可以显示步骤吗？

4

1 回答 1

13

有一种称为 Ford-Fulkerson 算法的算法，它可以在多项式时间内给出流网络的最大流量，您可以在 Kleinberg 和 Tardos 的《算法设计》一书中查找它，甚至可以在 CLRS 中查找。

解决问题所需要做的唯一事情是，您应该将无向 grah 中的每条边替换为具有相同容量的两条前后边，然后使用 Ford-Fulkerson 算法解决您的问题。可以很容易地证明，在这种转换中，流只通过两条边之一传播，并且总是不使用其中一条。

于 2015-06-05T10:05:41.270 回答