Matching (graph theory)

In the mathematical discipline of

A maximum matching (also known as maximum-cardinality matching^[2]) is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number ${\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 |E|=|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: ${\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

An induced matching is a matching that is the edge set of an induced subgraph.^[4]

Properties

In any graph without isolated vertices, the sum of the matching number and the

A spectral characterization of the matching number of a graph is given by Hassani Monfared and Mallik as follows: Let ${\displaystyle G}$ be a graph on ${\displaystyle n}$ vertices, and ${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}$ be ${\displaystyle k}$ distinct nonzero purely imaginary numbers where ${\displaystyle 2k\leq n}$. Then the

${\displaystyle G}$

${\displaystyle k}$

${\displaystyle A}$

${\displaystyle G}$

${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$

${\displaystyle n-2k}$

${\displaystyle G}$

${\displaystyle 2k}$

Note that the (simple) graph of a real symmetric or skew-symmetric matrix ${\displaystyle A}$ of order ${\displaystyle n}$ has ${\displaystyle n}$ vertices and edges given by the nonozero off-diagonal entries of ${\displaystyle A}$.

Matching polynomials

A generating function of the number of k-edge matchings in a graph is called a matching polynomial. Let G be a graph and m_k be the number of k-edge matchings. One matching polynomial of G is

${\displaystyle \sum _{k\geq 0}m_{k}x^{k}.}$

Another definition gives the matching polynomial as

${\displaystyle \sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},}$

where n is the number of vertices in the graph. Each type has its uses; for more information see the article on matching polynomials.

Algorithms and computational complexity

Maximum-cardinality matching

A fundamental problem in combinatorial optimization is finding a maximum matching. This problem has various algorithms for different classes of graphs.

In an unweighted bipartite graph, the optimization problem is to find a

In a

is used for this step, the running time of the Hungarian algorithm becomes ${\displaystyle O(V^{2}E)}$, or the edge cost can be shifted with a potential to achieve ${\displaystyle O(V^{2}\log {V}+VE)}$ running time with the

In a non-bipartite weighted graph, the problem of maximum weight matching can be solved in time ${\displaystyle O(V^{2}E)}$ using

Maximal matchings

A maximal matching can be found with a simple greedy algorithm. A maximum matching is also a maximal matching, and hence it is possible to find a largest maximal matching in polynomial time. However, no polynomial-time algorithm is known for finding a minimum maximal matching, that is, a maximal matching that contains the smallest possible number of edges.

A maximal matching with k edges is an

The number of matchings in a graph is known as the

The number of perfect matchings in a complete graph K_n (with n even) is given by the double factorial (n − 1)!!.^[13] The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the telephone numbers.^[14]

The number of perfect matchings in a graph is also known as the hafnian of its adjacency matrix.

Finding all maximally matchable edges

One of the basic problems in matching theory is to find in a given graph all edges that may be extended to a maximum matching in the graph (such edges are called maximally matchable edges, or allowed edges). Algorithms for this problem include:

• For general graphs, a deterministic algorithm in time ${\displaystyle O(VE)}$ and a randomized algorithm in time ${\displaystyle {\tilde {O}}(V^{2.376})}$.^[15][16]
• For bipartite graphs, if a single maximum matching is found, a deterministic algorithm runs in time ${\displaystyle O(V+E)}$.^[17]

Online bipartite matching

The problem of developing an online algorithm for matching was first considered by Richard M. Karp, Umesh Vazirani, and Vijay Vazirani in 1990.^[18]

In the online setting, nodes on one side of the bipartite graph arrive one at a time and must either be immediately matched to the other side of the graph or discarded. This is a natural generalization of the secretary problem and has applications to online ad auctions. The best online algorithm, for the unweighted maximization case with a random arrival model, attains a competitive ratio of 0.696.^[19]

Characterizations

Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs.

Applications

Matching in general graphs

• A Kekulé structure of an
  Friedrich August Kekulé von Stradonitz, who showed that benzene (in graph theoretical terms, a 6-vertex cycle) can be given such a structure.^[20]
• The Hosoya index is the number of non-empty matchings plus one; it is used in computational chemistry and mathematical chemistry investigations for organic compounds.
• The Chinese postman problem involves finding a minimum-weight perfect matching as a subproblem.

Matching in bipartite graphs

• Graduation problem is about choosing minimum set of classes from given requirements for graduation.
• Hitchcock transport problem involves bipartite matching as sub-problem.
• Subtree isomorphism problem involves bipartite matching as sub-problem.

See also

• Matching in hypergraphs - a generalization of matching in graphs.
• Fractional matching.
• Dulmage–Mendelsohn decomposition, a partition of the vertices of a bipartite graph into subsets such that each edge belongs to a perfect matching if and only if its endpoints belong to the same subset
• Edge coloring, a partition of the edges of a graph into matchings
• Matching preclusion, the minimum number of edges to delete to prevent a perfect matching from existing
• Rainbow matching, a matching in an edge-colored bipartite graph with no repeated colors
• Skew-symmetric graph, a type of graph that can be used to model alternating path searches for matchings
• Stable matching
  , a matching in which no two elements prefer each other to their matched partners
• Independent vertex set
  , a set of vertices (rather than edges) no two of which are adjacent to each other
• Stable marriage problem (also known as stable matching problem)

References