TOPICS
Search

Matching


A matching, also called an independent edge set, on a graph G is a set of edges of G such that no two sets share a vertex in common.

It is not possible for a matching on a graph with n nodes to exceed n/2 edges. When a matching with n/2 edges exists, it is called a perfect matching. When a matching exists that leaves a single vertex unmatched, it is called a near-perfect matching.

While not all graphs have perfect matchings, a largest matching (commonly known as a maximum matching or maximum independent edge set) exists for every graph. The size of this maximum matching is called the matching number of G and is denoted nu(G).

The number of matchings in a graph is sometimes called the Hosoya index.

A maximal independent edge set, which is different from a maximum independent edge set, is a matching that cannot be enlarged by simply adding an edge. Such matchings are easy to compute, but are not necessarily maximum independent edge sets. A maximal independent edge set on a general graph can be found using MaximalMatching[g] in the Wolfram Language package Combinatorica` , but not using a using built-in function in the Wolfram Language.

The blossom algorithm can be used to find a maximum independent edge set in a general graph, while the simpler Hungarian maximum matching algorithm can be used for bipartite graphs. A maximum independent edge set can be computed in the Wolfram Language using FindIndependentEdgeSet[g].

Let the number of distinct k-matchings of a graph with n vertices be denoted Phi_k. Then Phi_0(G)=1 (since the empty set consisting of no edges is always a 0-matching) and Phi_1(G)=m, where m is the edge count of G.

The matching polynomial is defined by

 mu(x)=sum_(k=0)^(nu(G))(-1)^kPhi_kx^(n-2k)

and the matching-generating polynomial by

 M(x)=sum_(k=0)^(nu(G))Phi_kx^k.

The numbers of distinct k-matchings for various specials classes of graphs are summarized in the following table, where n! denotes a factorial, n!! is a double factorial, (n; k) is a binomial coefficient, and delta_k is the discrete delta function.


See also

Berge's Theorem, Blossom Algorithm, Hosoya Index, Hungarian Maximum Matching Algorithm, Independent Edge Set, Marriage Theorem, Matching-Generating Polynomial, Matching Number, Matching Polynomial, Maximal Independent Edge Set, Maximum Independent Edge Set, Near-Perfect Matching, Perfect Matching, Stable Marriage Problem

Explore with Wolfram|Alpha

References

Hopcroft, J. and Karp, R. "An n^(5/2) Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.Pemmaraju, S. and Skiena, S. "Matching." §8.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 343-351, 2003.Skiena, S. "Matching." §6.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 240-246, 1990.Zwick, U. "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs." 2009. http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf.

Referenced on Wolfram|Alpha

Matching

Cite this as:

Weisstein, Eric W. "Matching." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Matching.html

Subject classifications