Perfect Matchings COMP 5703- Fall 2014

Matching A matching M of a graph G = (V,E) is a subset of edges with the property that no two edges of M share the same node, ie a set of pairwise non-adjacent edges. The matching problem is to find a maximum matching: the largest possible matching in a graph with V vertices is |V |/2, called a complete or perfect matching. Matched edges Refer to the edges in a matching M. Free edges Edges in E that are not in M. Mate If [u, v] is a matched edge, then u is the mate of v. Exposed vertices Vertices that are not incident upon any matched edges Alternating path A sequence of edges p = [u1, u2,..uk] where [u1, u2], [u3, u4],...[u2j−1, u2j],... are free, whereas [u2, u3], [u4, u5],...[u2j, u2j+1],... are matched. Outer vertices Those vertices on an alternating path that start with an exposed vertex and have have an odd rank (position) along the path. For example, from Figure 17, alternating path p1 = [v1, v4, v5, v6, v8, v7, v10, v9] of Graph G starts at exposed vertex v1 and has outer vertices v1, v5, v8, v10. Conversely, inner vertices satisfy the same criteria but have an even rank in the path. Augmenting Path An alternating path [u1, u2,...uk] where u1 and uk are exposed vertices. Figure 17 has an augmenting path p2 = [v1, v4, v5, v6, v8, v7, v10, v9] (highlighted in blue). 2 The Matching Proble