Matchings in graphs: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 1: Line 1:
== Definitions ==
== 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]].
# Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. A '''matching''' in <math>G</math> is a set <math>M\subseteq E</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 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 '''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>.

Revision as of 09:17, 21 November 2014

Definitions

  1. Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. A matching in [math]\displaystyle{ G }[/math] is a set [math]\displaystyle{ M\subseteq E }[/math] of edges such that no two edges in [math]\displaystyle{ M }[/math] are incident.
  2. A node [math]\displaystyle{ v\in V }[/math] is matched with respect to a matching [math]\displaystyle{ M }[/math] if it is incident to a member of [math]\displaystyle{ M }[/math]; otherwise, [math]\displaystyle{ v }[/math] is called free or exposed.
  3. A path [math]\displaystyle{ p }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called alternating with respect to some matching [math]\displaystyle{ M }[/math] if, for any two subsequent edges on [math]\displaystyle{ p }[/math], exactly one of them belongs to [math]\displaystyle{ M }[/math]. Consequently, the edges in [math]\displaystyle{ M }[/math] and the edges not in [math]\displaystyle{ M }[/math] appear strictly alternatingly on [math]\displaystyle{ p }[/math].
  4. A path [math]\displaystyle{ p }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called augmenting with respect to some matching [math]\displaystyle{ M }[/math] if [math]\displaystyle{ p }[/math] is alternating and both of its end nodes are exposed.
  5. Augmenting a matching [math]\displaystyle{ M }[/math] along an augmenting path [math]\displaystyle{ p }[/math] means:
    1. Each edge of [math]\displaystyle{ p }[/math] that was in [math]\displaystyle{ M }[/math] immediately before this augmentation step, is removed from [math]\displaystyle{ M }[/math].
    2. Each edge of [math]\displaystyle{ p }[/math] that was not in [math]\displaystyle{ M }[/math] immediately before this augmentation step, is inserted in [math]\displaystyle{ M }[/math].
Clearly, the size of [math]\displaystyle{ M }[/math] is increased by one.

Cardinality-maximal matching

Input: An undirected graph [math]\displaystyle{ G=(V,E) }[/math].

Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ |M'|\leq|M| }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].

Known algorithms:

  1. Maximum matching by Edmonds
  2. Classical bipartite cardinality matching

Maximum-weight matching

Input:

  1. An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
  2. A weight [math]\displaystyle{ w(e) }[/math] for each edge [math]\displaystyle{ e\in E }[/math].

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

Variations

  1. Bipartite matching: The graph [math]\displaystyle{ G=(V,E) }[/math] is bipartite.
  2. Perfect matching: A variant on the cardinality-maximal matching problem, in which [math]\displaystyle{ |V| }[/math] is even and the output is void if the maximal cardinality of any matching is strictly smaller than the upper bound [math]\displaystyle{ |V|/2 }[/math]. So the output is a matching if, and only if, it is of size [math]\displaystyle{ |V|/2 }[/math]. Such a matching is usually called a perfect matching.

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