Maximum flow in network

  • Thread starter Pietjuh
  • Start date
76
0
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 [tex]N_x=(V,A_x)[/tex] where [tex]A_x[/tex]
    is defined to be the union of two sets, [tex]B_1 = \{(i,j)\, |\, (i,j)\in A\, x_{ij} < b_ij\}[/tex] and [tex]B_2 = \{ (j,i)\, |\, (i,j)\in A\, x_{ij} > 0 \} [/tex], where [tex]x_{ij}[/tex] is the flow between vertex i and j, and [tex]b_{ij}[/tex] 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 [tex]\Delta = min(\Delta_1, \Delta_2)[/tex], [tex]\Delta_1 = min\{b_{ij} - x_{ij}\,|\, (i,j)\in B_1\}[/tex], [tex]\Delta_2 = min\{x_{ij}\,|\, (j,i) \in B_2\}[/tex]
  4. Add [tex]\Delta[/tex] to [tex]x_{ij}[/tex] 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 idea's how to solve it!

In every iteration there will be added an amount of [tex]\Delta[/tex] to the flow, which is the minimum of [tex]\Delta_1[/tex] and [tex]\Delta_2[/tex]. First determine if this minimum lies in [tex]\Delta_1[/tex] or in the other. If it lies in [tex]\Delta_2[/tex], changing the capacity will not have any effect. If it lies in [tex]\Delta_1[/tex] we can raise the capacity of that particulary branch (i,j) to the point that it not exceeds the minimum value of [tex]\Delta_2[/tex]. 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?
 
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.
 

Related Threads for: Maximum flow in network

Replies
1
Views
2K
  • Posted
Replies
3
Views
286
Replies
1
Views
1K
  • Posted
Replies
4
Views
1K
  • Posted
Replies
2
Views
2K
  • Posted
Replies
3
Views
2K
Replies
12
Views
1K
  • Posted
Replies
1
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top