How Does the Ford-Fulkerson Algorithm Determine Maximum Flow in a Network?

[Pietjuh]

Most of you have probably all heard of the max-flow min-cut theorem in graph theory. It says that in a network G=(V,A), the value of a maximum flow equals the capacity of a minimum cut. Then there is the Ford and Fulkerson algorithm to find a maximum flow in a network.

For the ones that don't really remember anymore how the algorithm works, i shall give a short summary:

1. Start with zero flow (x=0)
   
2. Construct a directed graph N_x=(V,A_x) where A_x
   is defined to be the union of two sets, B_1 = \{(i,j)\, |\, (i,j)\in A\, x_{ij} < b_ij\} and B_2 = \{ (j,i)\, |\, (i,j)\in A\, x_{ij} > 0 \}, where x_{ij} is the flow between vertex i and j, and b_{ij} is the capacity of the branch between i and j. The arrows in the first set are called forward arrows, and in the second set backward arrows. Choose a path P from vertex 1 to n. If it doesn't exist, go the the last step.
   
3. Determine \Delta = min(\Delta_1, \Delta_2), \Delta_1 = min\{b_{ij} - x_{ij}\,|\, (i,j)\in B_1\}, \Delta_2 = min\{x_{ij}\,|\, (j,i) \in B_2\}
   
4. Add \Delta to x_{ij} if (i,j) is a forward arrow of P, and substract it if (j,i) is a backward arrow of P and do nothing if (i,j) or (j,i) isn't an arrow of P.
5. Go to step 2
6. x is a maximal flow

Now I am wondering if we could adapt this algorithm a bit, to also find an arrow in G, if it exists, which has the property that when the capacity of the arrow is raised, the value of the maximum flow is raised. Here's my idea. I hope it will be correct, or that you will have some better ideas how to solve it!

In every iteration there will be added an amount of \Delta to the flow, which is the minimum of \Delta_1 and \Delta_2. First determine if this minimum lies in \Delta_1 or in the other. If it lies in \Delta_2, changing the capacity will not have any effect. If it lies in \Delta_1 we can raise the capacity of that particulary branch (i,j) to the point that it not exceeds the minimum value of \Delta_2. Now let's store this branch in a set called, say F. Isn't it true that when we finish with the algorithm, every branch in F has the property that when it's capacity is raised, the maximum flow will be higher?

 

[philosophking]

When you go and change the capacities like that, aren't you destroying your notion of "min-cut", so you'd have to go back and change things around? Maybe I'm not completely understanding the theorem.