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

Question

我正在学习Ford-Fulkerson算法，我知道我们需要后向边，因为我们选择的增加路径可能不会对最终的最大流量做出贡献。但我想知道是否存在一系列增强路径，以便不需要后向边缘？我试过很多例子，似乎确实存在，但我不知道如何证明它。

Answer 1

我理解我们需要反向边缘，因为我们选择的增加路径可能不会对最终的最大流量做出贡献。

我认为这不是真正的想法。您找到的从源到目标的每个流都必须贡献给最大流-否则，这不是最大流。我们绘制后向边，以便在存在其他流的情况下可以校正所选的增强路径。我正在试着解释更多。

我们可以使用DFS或BFS (normal graph traversing algorithm)找到从源到目标的边。然而，DFS和BFS的问题是，无论何时选择一条路径，您都会遇到该路径的瓶颈容量--即沿着该扩展路径的边的最小容量。但是，您可以使用其他方法更多地进入该路径。向后的边缘只是使您能够做到这一点。

我知道后向边对最小S-T剪切没有贡献，但是，后向边可以贡献最大流量，否则，您不能使用DFS或BFS纠正任意采用的路径。

希望这能有所帮助！