python - 如何计算具有无限容量的图中的最大流量

Question

我想实现一种方法，在至少包括一个无限容量的任何图中计算“最大流量”。我曾经在有图形处理时导入 NetworkX 库，但不幸的是，根据 maximum_flow 的描述，它没有考虑无限容量。 :

... If the graph has a path of infinite capacity, the value of a feasible flow on the graph is unbounded above and the function raises a NetworkXUnbounded.

所以，我的问题:

• 如何简单实现无限容量的Max-Flow？
• 是否可以为此调整 NetworkX 的方法？

欢迎任何其他建议。

谢谢

Answer 1

假设您有一个流网络，其中某些边具有无限容量。有两种可能的选择:

1. 有一条从源到无限容量边的汇的路径。在这种情况下，可以通过插入无限流穿过该路径来找到最大流。您无法通过在其他边缘插入更多流量来改善流量，因为您已经拥有无限流量!

2. 网络中不存在无限容量的路径。然后，网络中可以推送的总流量有一个上限(一个快速证明:将起始节点和无限容量边可到达的所有内容视为切割的一部分而形成切割，将其他所有内容视为切割的一部分)其他部分；则最大流量受该切口的容量限制)。在这种情况下，无限容量边缘的作用本质上是“您可以根据需要将尽可能多的流量推过该边缘”，但实际上没有任何流动路径可以有无限的流量通过。因此，将每个无限容量边替换为具有巨大但有限容量的边(例如，有限容量边的所有容量之和)。现在，此修改后的图中的最大流量为您提供原始网络中的最大流量。

希望这有帮助!