Maximum matching by Edmonds: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view == '''Definition:''' # A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some matching <math>M</m...") |
No edit summary |
||
| Line 1: | Line 1: | ||
== Abstract view == | == Abstract view == | ||
'''Invariant:''' | '''Invariant:''' | ||
| Line 12: | Line 8: | ||
'''Break condition:''' | '''Break condition:''' | ||
There is no more [[Matchings in graphs|augmenting path]]. | There is no more [[Matchings in graphs#Alternating and augmenting paths|augmenting path]]. | ||
== Induction basis == | == Induction basis == | ||
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.
Proof: Obvious.