In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a largest matching in a bipartite graph can be treated as a network flow problem. Finding a largest matching in a general graph is much more difficult; it can be done using Edmonds' blossom algorithm.
Definitions Given a graph G = (V, E), a matching M in G is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share common vertices.
M {\displaystyle M} is a matching of U ⊆ V {\displaystyle U\subseteq V} if every vertex in U {\displaystyle U} is incident with an edge in M {\displaystyle M} .
A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched (or unsaturated). A maximal matching is a matching M of a graph G that is not a subset of any other matching. A matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M. The following figure shows examples of maximal matchings (red) in three graphs.
A maximum matching (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number ν ( G ) {\displaystyle \nu (G)} of a graph G is the size of a maximum matching. Every maximum matching is maximal, but not every maximal matching is a maximum matching. The following figure shows examples of maximum matchings in the same three graphs.
A perfect matching is a matching that matches all vertices of the graph. That is, a matching is perfect if every vertex of the graph is incident to an edge of the matching. A matching is perfect if | M | = | V | / 2 {\displaystyle |M|=|V|/2} . Every perfect matching is maximum and hence maximal. In some literature, the term complete matching is used. In the above figure, only part (b) shows a perfect matching. A perfect matching is also a minimum-size edge cover. Thus, the size of a maximum matching is no larger than the size of a minimum edge cover: ν ( G ) ≤ ρ ( G ) {\displaystyle \nu (G)\leq \rho (G)} . A graph can only contain a perfect matching when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched. Clearly, a graph can only contain a near-perfect matching when the graph has an odd number of vertices, and near-perfect matchings are maximum matchings. In the above figure, part (c) shows a near-perfect matching. If every vertex is unmatched by some near-perfect matching, then the graph is called factor-critical. An induced matching is a matching that is the edge set of an induced subgraph.
Alternating and augmenting paths Given a matching M, an alternating path is a path that begins with an unmatched vertex and whose edges belong alternately to the matching and not to the matching. An augmenting path is an alternating path that starts from and ends on free (unmatched) vertices. Berge's lemma states that a matching M is maximum if and only if there is no augmenting path with respect to M {\displaystyle M} . Using Berge's lemma, we can start from any matching M {\displaystyle M} and repeatedly apply augmenting paths until no more augmenting paths are found. This reduces the problem of finding a large matching to finding augmented paths.
Properties In any graph without isolated vertices, the sum of the matching number and the edge covering number equals the number of vertices. If there is a perfect matching, then both the matching number and the edge cover number are |V | / 2.
… excerpt ends here. Continue reading the full article.
