algorithm - 福特富尔克森：后边条件

Question

我正在研究福特富尔克森，但对背景感到困惑。有人可以清除我直到什么时候或考虑图中背景的流量/容量条件应该是什么？因为我可以考虑任何边缘作为后端减去那么多流量并继续，这个过程可以继续下去。

请帮我。

谢谢

阿比纳夫

Answer 1

You use a "back edge" only if it's a part of a path P from s to t such that all capacities of the edges on the path greater than 0 (note that any path that fulfills this requirements increases the flow from s to t). An edge may be considered as a "back edge" if there's already flow greater than 0 on that edge, so you can "return" this flow. In that case the capacity of the edge will be the existing flow in it, when you do this, consider the edge's direction as opposite to the original direction.

Think about a graph with only vertices s and t and an edge between them with capacity c. at first you'll send c from s to t. now you can allegedly use this edge as a back edge, but note that when using it as a back edge it is directed from t to s and thus not a path from s to t.

Take a look at the wiki example to see how the back edge is being used there (from that example you can understand why the algorithm's running time is dependent on the edge's capacities).