在以下情况下，重新计算图中最大流量的最有效方法是什么：
- 我们将一侧的流量增加一
- 我们将一侧的流量减少一
在第一种情况下，是否足以运行一次福特-富克森算法的迭代？在第二种情况下，只有当边是一组最大流量的边的一部分时，我们才需要重新计算最大流量。运行一次 Ford-Fulkerson 迭代是否也足够？
问问题
2170 次
1 回答
1
在第一种情况下，“是”。这基本上就是福特-富克森的工作方式。想象一下，您在修改后的图表上从头开始运行 Ford-Fulkerson。您可以从运行与原始图表完全相同的步骤开始。要真正理解它的工作原理，看看最大流量与线性规划的关系可能会有所帮助（参见例如http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/NetFlow/max-flow -lp.html )。
在第二种情况下，如果你的容量都是整数，答案基本上是“是”。您要做的第一件事是修改旧的最大流量以满足新的约束。您可以通过基本上找到一条从源到汇的路径来沿着您的流穿过递减的边缘来做到这一点（这并不难做到，只需从递减的边缘开始并“跟随”流）。然后，为该路径中的每条边从流中减去 1。您现在有一个满足约束的流程，但可能不是最佳的。然而，它最多只比最优流量少 1，因此 Ford-Fulkerson 的一次迭代将再次起作用。
在非整数情况下，事情可能会更复杂，在最坏的情况下，您必须基本上重新解决问题。我不熟悉这里的最佳算法，但您可以搜索“动态最大流量”。另请参阅https://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs。
于 2016-06-14T17:11:30.660 回答