Alternating paths algorithm: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Category:Algorithm]] | [[Category:Algorithm]] | ||
[[Category:Maximum matching problem]] | [[Category:Maximum matching problem]] | ||
'''Algorithmic problem:''' The graph <math>G</math> is biparite. | |||
'''Type of algorithm:''' loop | |||
'''Auxillary data:''' | |||
== Abstract view == | |||
'''Invariant:''' Before and after each iteration, <math>M</math> is a matching. | |||
'''Variant:''' <math>|M|</math> increases by <math>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 | |||
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