algorithm - 识别增加图中最大流量的边

Question

我必须找到图的最大流，然后识别边，这样如果边的容量增加，图的最大流也会增加。

我已经通过应用 Relabel-To-Front 算法成功找到了最大流量，但似乎想不出一种方法来找出哪些边缘有可能增加最大流量。

提前谢谢你。

Answer 1

您可以通过解决最大流问题的对偶问题找到这样的边:min-cut problem .
max-flow min-cut theorem 的后果是在你的图上形成最小切割的边缘实际上是最大流中的饱和边缘。
因此，如果存在可能增加图中最大流的边，则它们是最小割的一部分。
但是不能保证你的图中存在一条边，增加这条边的流量会导致更大的流量。在某些情况下，您需要增加图形所有边的容量以增加最大流量。

一种测试方法是计算最小切割，然后尝试增加该最小切割的一条或多条边上的容量，并重新计算流以与之前的值进行比较。