Alternating paths algorithm: Difference between revisions
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
== Abstract view == | == Abstract view == | ||
'''Invariant:''' Before and after each iteration, <math>M</math> is a matching. | '''Invariant:''' Before and after each iteration, <math>M</math> is a matching. | ||
'''Variant:''' <math>|M|</math> increases by <math>1</math>. | '''Variant:''' <math>|M|</math> increases by <math>1</math>. | ||
Break condition: There is no more augmenting alternating path. | Break condition: There is no more augmenting alternating path. | ||
Revision as of 13:01, 27 January 2015
Algorithmic problem: The graph [math]\displaystyle{ G }[/math] is biparite. Type of algorithm: loop Auxillary data:
Abstract view
Invariant: Before and after each iteration, [math]\displaystyle{ M }[/math] is a matching. Variant: [math]\displaystyle{ |M| }[/math] increases by [math]\displaystyle{ 1 }[/math].
Break condition: There is no more augmenting alternating path.
Induction basis
Abstract view: is initialized to be some matching, for example, . Implementation: Obvious. Proof: Nothing to show.
Induction step
Abstract view: If there is an augmenting alternating path, use it to increase ; otherwise, terminate the algorithm and return . Implementation: Call the algorithm Find augmenting alternating path. If this call fails, terminate the algorithm and return . Otherwise, let denote the set of all edges on the path delivered by that call. Let be the symmetric difference of and Correctness:
Complexity
Statement: Proof:
Further information