algorithm - 是否存在不需要后向边缘的增广路径序列？

Question

我正在学习 Ford-Fulkerson 算法，并且我知道我们需要后向边缘，因为我们选择的增强路径可能对最终的最大流量没有贡献。但我想知道是否存在一系列不需要后向边缘的增广路径？我尝试了很多例子，似乎存在，但我不知道如何证明。

标签： algorithmgraphmax-flowford-fulkerson

Answer 1

我知道我们需要后向边缘，因为我们选择的增强路径可能对最终的最大流量没有贡献。

我认为这不是实际的想法。您从源到目的地找到的每一个流都必须贡献给最大流 - 否则，这不是最大值。我们绘制后向边缘，以便在有其他流时我们可以更正选定的增广路径。我试图解释更多。

我们可以使用 DFS 或 BFS（普通图遍历算法）找到从源到目标的边。但是，DFS 和 BFS 的问题在于，无论何时选择一条路径，都会遇到该路径的瓶颈容量——即沿该增广路径的边的最小容量。但是，您可以使用其他方式更多地进入该路径。向后的边缘只是使您能够这样做。

我知道后向边缘对最小 ST 切割没有贡献，但是，后向边缘可以对最大流量做出贡献，否则，您无法更正使用 DFS 或 BFS 任意采用的路径。

希望有帮助！