Maximum matching by Edmonds: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 11: | Line 11: | ||
'''Definition:''' | '''Definition:''' | ||
A '''blossom''' is a cycle <math>C</math> of odd lengths in <math>G</math> such that <math>\lfloor|C|/2\rfloor< | A '''blossom''' is a cycle <math>C</math> of odd lengths in <math>G</math> such that <math>\lfloor|C|/2\rfloor</math> edges on <math>C</math> are matched and the remaining node is matched as well (by an edge not on <math>C</math>, in fact). | ||
== Induction basis == | == Induction basis == | ||
Revision as of 17:10, 21 November 2014
Abstract view
Invariant: The current selection [math]\displaystyle{ M }[/math] of edges is a matching.
Variant: Either the cardinality of [math]\displaystyle{ M }[/math] increases, or the number of nodes of [math]\displaystyle{ G }[/math] decreases.
Break condition: There is no more augmenting path.
Definition: A blossom is a cycle [math]\displaystyle{ C }[/math] of odd lengths in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \lfloor|C|/2\rfloor }[/math] edges on [math]\displaystyle{ C }[/math] are matched and the remaining node is matched as well (by an edge not on [math]\displaystyle{ C }[/math], in fact).
Induction basis
Abstract view: Start with some matching, for example, the empty matching.
Induction step
Apply the