Successive shortest paths: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 4: | Line 4: | ||
# The capacity constraints are fulfilled, that is, <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>. | # The capacity constraints are fulfilled, that is, <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>. | ||
# The '''balance discrepancy''' of each node <math>v\in V</math> is '''underestimating''', that is, | # The '''balance discrepancy''' of each node <math>v\in V</math> is '''underestimating''', that is, | ||
## If <math>b(v)>0</math>, then <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\leq b(v)</math>. | |||
## If <math>b(v)<0</math>, then <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\geq b(v)</math>. | |||
## If <math>b(v)=0</math>, then <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v)</math>. | |||
'''Variant:''' | '''Variant:''' | ||
The '''balance discrepancy''' strictly decreases, that is, the value | The '''total balance discrepancy''' strictly decreases, that is, the value | ||
:<math>\sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right|</math>. | :<math>\sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right|</math>. | ||
| Line 12: | Line 16: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
Start with | Start with the zero flow. | ||
'''Proof:''' | |||
Obvious. | |||
Revision as of 08:49, 23 October 2014
Abstract view
Invariant:
- The capacity constraints are fulfilled, that is, [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
- The balance discrepancy of each node [math]\displaystyle{ v\in V }[/math] is underestimating, that is,
- If [math]\displaystyle{ b(v)\gt 0 }[/math], then [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\leq b(v) }[/math].
- If [math]\displaystyle{ b(v)\lt 0 }[/math], then [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\geq b(v) }[/math].
- If [math]\displaystyle{ b(v)=0 }[/math], then [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v) }[/math].
Variant:
The total balance discrepancy strictly decreases, that is, the value
- [math]\displaystyle{ \sum_{v\in V}\left|\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)\right| }[/math].
Induction basis:
Abstract view: Start with the zero flow.
Proof: Obvious.