Maximum matching by Edmonds: Difference between revisions
Jump to navigation
Jump to search
| Line 20: | Line 20: | ||
== Induction step == | == Induction step == | ||
Apply the | '''Abstract view:''' | ||
# Apply the modified graph search from the [[Classical bipartite cardinality matching#Induction step|classical algorithm]] for the restriction to [[Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]]. | |||
# However, in addition, each node has a boolean label even/odd, which is set when the graph search sees the node for the very first time. More specifically, for each node this is the parity of the distance from the start node in the arborescence. | |||
'''Implementation of step 1:''' | |||
Revision as of 18:06, 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
Abstract view:
- Apply the modified graph search from the classical algorithm for the restriction to bipartite graphs.
- However, in addition, each node has a boolean label even/odd, which is set when the graph search sees the node for the very first time. More specifically, for each node this is the parity of the distance from the start node in the arborescence.
Implementation of step 1: