I'm learning the Ford-Fulkerson method nowadays. Some articles say If f is a maximum flow, then there's no augmenting path! But if there's no augmenting path, how do you know f is maximum flow? How do you know the way finding augmenting path is correct? In the residual network, why if we can't reach t from s there is no way to increase flow? How do you know that?

algorithmoptimizationmathematical-optimizationmax-flowford-fulkerson

Reputation: 1

Questions on Augmenting path (Ford-Fulkerson method)

I'm learning the Ford-Fulkerson method nowadays.

Some articles say If f is a maximum flow, then there's no augmenting path! But if there's no augmenting path, how do you know f is maximum flow?

How do you know the way finding augmenting path is correct?
In the residual network, why if we can't reach t from s there is no way to increase flow? How do you know that?

Upvotes: 0

Answers (1)

fuglede

Reputation: 18201

This is the Max-flow min-cut theorem, cf. e.g. Theorem 26.6 in CLRS. The gist is the following: Let S be the set of vertices accessible from the source in the residual network, and let T = V \ S. Then, if there are no augmenting paths, (S, T) is a cut, and one finds that the value of the flow is the capacity of this cut. Since flow values can never exceed cut capacities, it follows that the flow is maximal.

Upvotes: 0

Questions on Augmenting path (Ford-Fulkerson method)

Answers (1)

Related Questions