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