Successive shortest paths: Difference between revisions
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
'''Definition:''' | '''Definition:''' | ||
# For a node <math>v\in V</math>, let <math>\Delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)</math>. | # For a node <math>v\in V</math>, let <math>\Delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)</math>. | ||
# The '''imbalance''' of a node <math>v\in V</math> is defined as <math>\Delta f(v)-b(v)</math>. | # The '''imbalance''' of a node <math>v\in V</math> is defined as <math>I_f(v):=\Delta f(v)-b(v)</math>. | ||
# The imbalance of a node <math>v\in V</math> is '''underestimating''' if <math>0\leq \Delta f(v)\leq b(v)</math> or <math>0\geq\Delta f(v)\geq b(v)</math>. | # The imbalance of a node <math>v\in V</math> is '''underestimating''' if <math>0\leq \Delta f(v)\leq b(v)</math> or <math>0\geq\Delta f(v)\geq b(v)</math>. | ||
# The '''total imbalance''' of <math>f</math> is the defined as <math>\sum_{v\in V}| | # The '''total imbalance''' of <math>f</math> is the defined as <math>\sum_{v\in V}|I_f(v)</math>. | ||
'''Invariant:''' | '''Invariant:''' | ||
Revision as of 10:39, 23 October 2014
Abstract view
Definition:
- For a node [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ \Delta f(v):=\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v) }[/math].
- The imbalance of a node [math]\displaystyle{ v\in V }[/math] is defined as [math]\displaystyle{ I_f(v):=\Delta f(v)-b(v) }[/math].
- The imbalance of a node [math]\displaystyle{ v\in V }[/math] is underestimating if [math]\displaystyle{ 0\leq \Delta f(v)\leq b(v) }[/math] or [math]\displaystyle{ 0\geq\Delta f(v)\geq b(v) }[/math].
- The total imbalance of [math]\displaystyle{ f }[/math] is the defined as [math]\displaystyle{ \sum_{v\in V}|I_f(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 imbalance of every node is underestimating.
Variant: The total imbalance strictly decreases.
Break condition: The imbalances of all nodes are zero.
Induction basis
Abstract view: Start with the zero flow.
Proof: Obvious.
Induction step
- Find a shortest path from with minimum