Dinic: Difference between revisions
Jump to navigation
Jump to search
| Line 24: | Line 24: | ||
== Induction step == | == Induction step == | ||
'''Abstract view:''' | |||
# Construct the [[Basic graph definitions|subgraph]] <math>G'=(V,A')</math> of the residual network that contains an arc if, and only if, the arc is on at least one <math>(s,t)</math>-path with smallest number of arcs. | # Construct the [[Basic graph definitions|subgraph]] <math>G'=(V,A')</math> of the residual network that contains an arc if, and only if, the arc is on at least one <math>(s,t)</math>-path with smallest number of arcs. | ||
# Construct a blocking flow <math>f'</math> in <math>G'</math> wth respect to the residual capacities for <math>f</math>. | # Construct a blocking flow <math>f'</math> in <math>G'</math> wth respect to the residual capacities for <math>f</math>. | ||
# For all arcs <math>a\in A</math>, add <math>f'</math> to <math>f</math>. | # For all arcs <math>a\in A</math>, add <math>f'</math> to <math>f</math>. | ||
Revision as of 13:46, 13 October 2014
General Information
Algorithmic problem: Max-Flow Problems
Type of algorithm : loop.
Abstract View
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations: The flow [math]\displaystyle{ f }[/math] is feasible. If all upper bounds are integral, the [math]\displaystyle{ f }[/math]-values are integral as well.
Variant: The smallest number of arcs on a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path strictly increases.
Induction basis
Abstract view: Initialize [math]\displaystyle{ f }[/math] as an arbitrary feasible flow, for example, the zero flow.
Proof: Nothing to show.
Induction step
Abstract view:
- Construct the subgraph [math]\displaystyle{ G'=(V,A') }[/math] of the residual network that contains an arc if, and only if, the arc is on at least one [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs.
- Construct a blocking flow [math]\displaystyle{ f' }[/math] in [math]\displaystyle{ G' }[/math] wth respect to the residual capacities for [math]\displaystyle{ f }[/math].
- For all arcs [math]\displaystyle{ a\in A }[/math], add [math]\displaystyle{ f' }[/math] to [math]\displaystyle{ f }[/math].