View source for Matchings in graphs

== Definitions ==

# Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. A '''matching''' in <math>G</math> is a set <math>M</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]].
# A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a member of <math>M</math>; otherwise, <math>v</math> is called '''free''' or '''exposed'''.
# A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some matching <math>M</math> if, for any two subsequent edges on <math>p</math>, exactly one of them belongs to <math>M</math>. Consequently, the edges in <math>M</math> and the edges not in <math>M</math> appear strictly alternatingly on <math>p</math>.
# A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''augmenting''' with respect to some matching <math>M</math> if <math>p</math> is alternating and both of its end nodes are exposed.

== Cardinality-maximal matching ==

'''Input:'''
An undirected graph <math>G=(V,E)</math>.

'''Output:'''
A matching <math>M</math> in <math>G</math> such that <math>|M'|\leq|M|</math> for any other matching <math>M'</math> in <math>G</math>.

'''Known algorithms:'''
# [[Maximum matching by Edmonds]]

== Maximum-weight matching ==

'''Input:'''
# An undirected graph <math>G=(V,E)</math>.
# A '''weight''' <math>w(e)</math> for each edge <math>e\in E</math>.

'''Output:'''
A matching <math>M</math> in <math>G</math> such that <math>\sum_{e\in M'}w(e)\leq\sum_{e\in M}w(e)</math> for any other matching <math>M'</math> in <math>G</math>.

== Variations ==

# '''Bipartite matching:''' The graph <math>G=(V,E)</math> is [[Basic graph definitions#Bipartite and k-partite graphs|bipartite]].
# '''Perfect matching:''' A variant on the cardinality-maximal matching problem, in which <math>|V|</math> is even and the output is void if the maximal cardinality of any matching is strictly smaller than the upper bound <math>|V|/2</math>.

'''Remark:'''
The maximum weight matching restricted to bipartite graphs is usually called the '''assignment problem'''.