Alternating paths algorithm: Difference between revisions
No edit summary |
|||
| (9 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
[[Category:Maximum matching problem]] | [[Category:Maximum matching problem]] | ||
'''Algorithmic Problem:''' [[Matchings in graphs]]. | |||
'''Prerequisites:''' The graph <math>G</math> is [[Bipartite graph|bipartite]]. | |||
'''Type of algorithm:''' loop | |||
'''Auxillary data:''' | |||
== Abstract view == | == 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 == | == Induction basis == | ||
'''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\ | '''Abstract view:''' <math>M</math> is initialized to be some matching, for example, <math>M:=\empty</math>. | ||
'''Implementation:''' Obvious. | '''Implementation:''' Obvious. | ||
'''Proof:''' Nothing to show. | '''Proof:''' Nothing to show. | ||
== Induction step == | == Induction step == | ||
'''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:''' | |||
# Call the algorithm Find augmenting alternating path. | # Call the algorithm Find augmenting alternating path. | ||
# If this call fails, terminate the algorithm and return <math>M</math>. | # If this call fails, terminate the algorithm and return <math>M</math>. | ||
# Otherwise, let <math>E'</math> denote the set of all edges on the path delivered by that call. | # Otherwise, let <math>E'</math> denote the set of all edges on the path delivered by that call. | ||
# Let <math>M</math> be the [http://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] of <math>M</math> and <math | # Let <math>M</math> be the [http://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] of <math>M</math> and <math>???</math> | ||
Correctness: | Correctness: | ||
== Complexity == | == Complexity == | ||
'''Statement:''' | |||
'''Proof:''' | |||
==Further information== | ==Further information== | ||
Latest revision as of 13:38, 27 January 2015
Algorithmic Problem: Matchings in graphs.
Prerequisites: The graph [math]\displaystyle{ G }[/math] is bipartite.
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:=\empty }[/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]\displaystyle{ ??? }[/math]
Correctness:
Complexity
Statement:
Proof: