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

Question

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

...如果图形具有无限容量的路径，则图形上的可行流的值在上面是无界的，并且该函数引发NetworkXUnbounded。

所以，我的问题：

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

欢迎任何其他建议。

谢谢

Answer 1

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

1. 从无限容量边缘的源到汇的路径。在这种情况下，通过推动该路径上的无限流量可以找到最大流量。由于你已经拥有无限流量，你无法通过推动更多流量穿过其他边缘来改善流量！
2. 网络中不存在无限容量路径。然后有一个上限可以在网络中推送多少总流量（快速证明：考虑通过将起始节点和无限容量边缘可达到的所有内容作为切割的一部分形成的切割，以及其他所有内容作为切割其他部分;然后最大流量受切割能力的限制。在这种情况下，无限容量边缘的功能基本上是“你可以按照你想要的那样在这个边缘上推动尽可能多的流量”，但是没有流动路径实际上可以有无限流量穿过它。因此，取每个无限容量边缘并用具有巨大但有限容量的边缘（例如，有限容量边缘的所有容量的总和）替换它。现在，此修改图中的最大流量为您提供原始网络中的最大流量。

希望这可以帮助！