Matchings in graphs

From Algowiki
Jump to: navigation, search

Matchings

  1. Let [math]G=(V,E)[/math] be an undirected graph. Without loss of generality, [math]G[/math] is connected. 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 incident.
  2. An edge in [math]M[/math] is called matched, an edge in [math]E\setminus M[/math] is unmatched.
  3. A node [math]v\in V[/math] is matched with respect to a matching [math]M[/math] if it is incident to a matched edge; otherwise, [math]v[/math] is called free or exposed.
  4. A matching is called perfect if there is no exposed node.

Remark: A perfect matching [math]M[/math] is only possible if [math]|V|[/math] is even. Then [math]M[/math] is perfect if, and only if, [math]|M|=|V|/2[/math].

Alternating and augmenting paths

  1. 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 successive edges on [math]p[/math], exactly one of them belongs to [math]M[/math]. In other words, the edges in [math]M[/math] and the edges not in [math]M[/math] appear strictly alternatingly on [math]p[/math].
  2. An alternating 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 both of its end nodes are exposed.
  3. Augmenting a matching [math]M[/math] along an augmenting path [math]p[/math] means increasing the size of [math]M[/math] by one as follows:
    1. Each edge of [math]p[/math] that was in [math]M[/math] immediately before this augmentation step, is removed from [math]M[/math].
    2. Each edge of [math]p[/math] that was not in [math]M[/math] immediately before this augmentation step, is inserted in [math]M[/math].

Finding augmenting paths

To find alternating paths in a matching [math]M[/math], a graph traversal strategy is chosen and modified as follows:

  1. Whenever the current node [math]v[/math] has been reached via an edge in [math]M[/math], only incident edges in [math]E\setminus M[/math] are considered for seeing new nodes.
  2. Mirror-symmetrically, whenever the current node [math]v[/math] has been reached via an edge in [math]E\setminus M[/math], only the (unique) incident edge in [math]M[/math], if existing, is considered for seeing a new node.

To find augmenting paths, the start node must be an exposed node.

Remark on the implementation: This modified graph traversal in an undirected graph could be implemented as an ordinary graph traversal in a directed graph:

  1. Duplicate each matched node [math]v[/math] giving [math]v_1[/math] and [math]v_2[/math].
  2. Replace each edge [math]\{v,w\}[/math] by two arcs, [math](v,w)[/math] and [math](w,v)[/math].
  3. For each matched node [math]v[/math]:
    1. Let all incoming arcs of [math]v[/math] in [math]M[/math] point to [math]v_1[/math] and all outgoing arcs in [math]E\setminus M[/math] leave [math]v_1[/math].
    2. Mirror-symmetrically, let all incoming arcs of [math]v[/math] in [math]E\setminus M[/math] point to [math]v_2[/math] and all outgoing arcs of [math]v[/math] in [math]M[/math] leave [math]v_2[/math].

Caveat: If the graph is not bipartite, no graph traversal strategies, modified as described above, guarantees to find an augmenting path if there is one; blossom handling is necessary in addition.

Blossoms

Definitions:

  1. For a matching [math]M[/math] in [math]G[/math], a blossom is a cycle [math]B[/math] of odd length in [math]G[/math] such that [math]\lfloor|B|/2\rfloor[/math] edges on [math]B[/math] are matched and the remaining node on [math]B[/math] is matched as well (by an edge not on [math]B[/math], in fact).
  2. The unique matched edge with exactly one incident node on [math]B[/math] is called the stem of the blossom.
  3. Shrinking a blossom [math]B[/math] means:
    1. Insert a new node [math]u_B[/math] in [math]V[/math].
    2. For each edge [math]\{v,w\}[/math] such that [math]v[/math] is on [math]B[/math] and [math]w[/math] is not: Replace [math]\{v,w\}[/math] by a new edge [math]\{u_B,w\}[/math].
    3. Remove all nodes and edges on [math]B[/math].
  4. An augmenting path [math]p[/math] conforms to [math]B[/math] if [math]p[/math] contains the stem.

Statement: Let [math]G=(V,E)[/math] be an undirected graph, [math]M[/math] a matching in [math]G[/math], and [math]B[/math] a blossom. Further, let [math]G'=(V',E')[/math] be the undirected graph resulting from shrinking [math]B[/math], and let [math]M'[/math] be the restriction of [math]M[/math] to [math]G'[/math]. There is an augmenting path conforming to [math]B[/math] in [math]G[/math] with respect to [math]M[/math] if, and only if, there is an augmenting path in [math]G'[/math] with respect to [math]M'[/math] that contains [math]u_B[/math].

Proof: First suppose there is a conforming augmenting path [math]p[/math] in [math]G[/math] with respect to [math]M[/math]. According to either possible orientation of [math]p[/math], let [math]s[/math] and [math]t[/math] denote the first and the last node of [math]p[/math]. Moreover, let [math]v[/math] and [math]w[/math] denote the first and the last node of [math]p[/math] that also belongs to [math]B[/math] (possibly [math]v=w[/math]). The concatenation of the subpaths of [math]p[/math] from [math]s[/math] to [math]v[/math] and from [math]w[/math] to [math]t[/math] is an augmenting path in [math]G'[/math], and this path contains [math]u_B[/math].

So, consider the case that there is an augmenting path [math]p[/math] in [math]G'[/math] with respect to [math]M'[/math], and that [math]p[/math] contains [math]u_B[/math]. Since [math]u_B[/math] is matched, [math]u_B[/math] is not an end node of [math]p[/math], so [math]p[/math] contains the stem of [math]B[/math] because this is the only matched edge incident to [math]u_B[/math]. Let [math]v[/math] be the node of [math]B[/math] incident to the stem and let [math]w[/math] be the node on [math]p[/math] that is farthest away from [math]v[/math] on [math]p[/math] among all nodes of [math]p[/math] that also belong to [math]B[/math]. Exactly one of the two subpaths of [math]B[/math] from [math]v[/math] to [math]w[/math] yields a conforming augmenting path by concatenation with the two subpaths of [math]p[/math] from the end nodes of [math]p[/math] up to [math]v[/math] and [math]w[/math], respectively.