Maximum matching by Edmonds: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 14: | Line 14: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
Start with some matching, for example, the empty matching. | Start with some matching, for example, the empty matching. | ||
== Induction step == | == Induction step == | ||
Revision as of 12:45, 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.
Induction basis
Abstract view: Start with some matching, for example, the empty matching.