37.9k views
0 votes
Suppose that we redefine the residual network to disallow edges into s. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.

1 Answer

3 votes

I think your intuitive ideas are already quite enough for a proof. Let's consider two graphs: in a graph G1 we allow edges into s, and in a graph G2 we do not.

Now, suppose the Ford-Fulkerson algorithm finds a larger flow in G1 then it does in G2. As all augmenting paths in G2 are also valid in G1, we can use the same augmenting paths on both graphs for as long as possible, and then obtain a state for the residual network in which there is an augmenting path in G1, but not in G2.

However, as you pointed out, any augmenting path that is valid in G1 is also valid in G2, provided that we remove every edge that comes before the last visit to s. Therefore our assumption is wrong and such a situation cannot exist -- Ford-Fulkerson will produce the same output on both G1 and G2.

User Anatoli
by
6.9k points