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.