Matchings in graphs

Matchings

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

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

Alternating and augmenting paths

1. 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 successive edges on [math]\displaystyle{ p }[/math], exactly one of them belongs to [math]\displaystyle{ M }[/math]. In other words, the edges in [math]\displaystyle{ M }[/math] and the edges not in [math]\displaystyle{ M }[/math] appear strictly alternatingly on [math]\displaystyle{ p }[/math].
2. An alternating 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 both of its end nodes are exposed.
3. Augmenting a matching [math]\displaystyle{ M }[/math] along an augmenting path [math]\displaystyle{ p }[/math] means increasing the size of [math]\displaystyle{ M }[/math] by one as follows:
   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].

Finding augmenting paths

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

1. Whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ M }[/math], only incident edges in [math]\displaystyle{ E\setminus M }[/math] are considered for seeing new nodes.
2. Mirror-symmetrically, whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ E\setminus M }[/math], only the (unique) incident edge in [math]\displaystyle{ 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]\displaystyle{ v }[/math] giving [math]\displaystyle{ v_1 }[/math] and [math]\displaystyle{ v_2 }[/math].
2. Replace each edge [math]\displaystyle{ \{v,w\} }[/math] by two arcs, [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math].
3. For each matched node [math]\displaystyle{ v }[/math]:
   1. Let all incoming arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ M }[/math] point to [math]\displaystyle{ v_1 }[/math] and all outgoing arcs in [math]\displaystyle{ E\setminus M }[/math] leave [math]\displaystyle{ v_1 }[/math].
   2. Mirror-symmetrically, let all incoming arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ E\setminus M }[/math] point to [math]\displaystyle{ v_2 }[/math] and all outgoing arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ M }[/math] leave [math]\displaystyle{ 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]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math], a blossom is a cycle [math]\displaystyle{ B }[/math] of odd length in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \lfloor|B|/2\rfloor }[/math] edges on [math]\displaystyle{ B }[/math] are matched and the remaining node on [math]\displaystyle{ B }[/math] is matched as well (by an edge not on [math]\displaystyle{ B }[/math], in fact).
2. The unique matched edge with exactly one incident node on [math]\displaystyle{ B }[/math] is called the stem of the blossom.
3. Shrinking a blossom [math]\displaystyle{ B }[/math] means:
   1. Insert a new node [math]\displaystyle{ v_B }[/math] in [math]\displaystyle{ V }[/math].
   2. For each edge [math]\displaystyle{ \{v,w\} }[/math] such that [math]\displaystyle{ v }[/math] is on [math]\displaystyle{ B }[/math] and [math]\displaystyle{ w }[/math] is not: Replace [math]\displaystyle{ \{v,w\} }[/math] by a new edge [math]\displaystyle{ \{v_B,w\} }[/math].
   3. Remove all nodes and edges on [math]\displaystyle{ B }[/math].
4. An augmenting path [math]\displaystyle{ p }[/math] conforms to [math]\displaystyle{ B }[/math] if [math]\displaystyle{ p }[/math] contains the stem.

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

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

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