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

Question

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

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

提前致谢。

Answer 1

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

一种测试方法是计算 min-cut，然后尝试增加此 min-cut 的一条或多条边上的容量，然后重新计算流以与之前的值进行比较。