Alternating paths algorithm: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 4: | Line 4: | ||
'''Algorithmic problem:''' The graph <math>G</math> is biparite. | '''Algorithmic problem:''' The graph <math>G</math> is biparite. | ||
'''Type of algorithm:''' loop | '''Type of algorithm:''' loop | ||
'''Auxillary data:''' | '''Auxillary data:''' | ||
| Line 10: | Line 12: | ||
'''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. | ||
| Line 16: | Line 20: | ||
'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>. | '''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty1</math>. | ||
'''Implementation:''' Obvious. | '''Implementation:''' Obvious. | ||
'''Proof:''' Nothing to show. | '''Proof:''' Nothing to show. | ||
| Line 22: | Line 28: | ||
'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>. | '''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>. | ||
'''Implementation:''' | '''Implementation:''' | ||
# Call the algorithm Find augmenting alternating path. | # Call the algorithm Find augmenting alternating path. | ||
Revision as of 13:16, 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: [math]\displaystyle{ M }[/math] is initialized to be some matching, for example, [math]\displaystyle{ M:=\empty1 }[/math].
Implementation: Obvious.
Proof: Nothing to show.
Induction step
Abstract view: If there is an augmenting alternating path, use it to increase [math]\displaystyle{ M }[/math]; otherwise, terminate the algorithm and return [math]\displaystyle{ M }[/math].
Implementation:
- Call the algorithm Find augmenting alternating path.
- If this call fails, terminate the algorithm and return [math]\displaystyle{ M }[/math].
- Otherwise, let [math]\displaystyle{ E' }[/math] denote the set of all edges on the path delivered by that call.
- Let [math]\displaystyle{ M }[/math] be the symmetric difference of [math]\displaystyle{ M }[/math] and <math<???</math>
Correctness:
Complexity
Statement:
Proof: