Successive shortest paths: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 2: | Line 2: | ||
'''Definition:''' | '''Definition:''' | ||
# The ''' | # The '''imbalance''' of a node <math>v\in V</math> is defined as <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v)</math>. | ||
# The | # The imbalance 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>. | ||
# The '''total imbalance''' is the sum of the absolute values of all imbalances, taken over all nodes. | |||
'''Invariant:''' | '''Invariant:''' | ||
# 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>. | ||
# There is no negative cycle in the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>. | # There is no negative cycle in the [[Basic flow definitions#Residual network|residual network]] of <math>f</math>. | ||
# The | # The imbalance of ever node is underestimating. | ||
'''Variant:''' | '''Variant:''' | ||
The | The total imbalance strictly decreases. | ||
== Induction basis == | == Induction basis == | ||
Revision as of 10:26, 23 October 2014
Abstract view
Definition:
- The imbalance of a node [math]\displaystyle{ v\in V }[/math] is defined as [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)-b(v) }[/math].
- The imbalance 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].
- The total imbalance is the sum of the absolute values of all imbalances, taken over all nodes.
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 imbalance of ever node is underestimating.
Variant: The total imbalance strictly decreases.
Induction basis
Abstract view: Start with the zero flow.
Proof: Obvious.
Induction step
- If there