Successive shortest paths: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 1: | Line 1: | ||
== Abstract view == | == Abstract view == | ||
''' | '''Definition:''' | ||
# The | # The '''balance discrepancy''' of a node <math>v\in V</math> is defined as | ||
# The | # The balance discrepancy of a node <math>v\in V</math> is '''underestimating''' if: | ||
## 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)\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)\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>. | ## 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>. | ||
'''Invariant:''' | |||
# The capacity constraints are fulfilled, that is, <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>. | |||
# There is no negative cycle in the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>. | |||
# The balance discrepancy of ever node is underestimating. | |||
'''Variant:''' | '''Variant:''' | ||
| Line 20: | Line 25: | ||
'''Proof:''' | '''Proof:''' | ||
Obvious. | Obvious. | ||
== Induction step == | |||
# If there | |||
# | |||
Revision as of 08:58, 23 October 2014
Abstract view
Definition:
- The balance discrepancy of a node [math]\displaystyle{ v\in V }[/math] is defined as
- The balance discrepancy of a node [math]\displaystyle{ v\in V }[/math] is underestimating if:
- 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].
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].
- There is no negative cycle in the residual network of [math]\displaystyle{ f }[/math].
- The balance discrepancy of ever node is underestimating.
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.
Induction step
- If there