Perfect matching

Last updated September 15, 2024

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph $G = (V, E)$ , a perfect matching in $G$ is a subset $M$ of edge set $E$ , such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$ .

A perfect matching can only occur when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.

Characterizations

Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching.

The Tutte theorem provides a characterization for arbitrary graphs.

A perfect matching is a spanning 1-regular subgraph, a.k.a. a 1-factor. In general, a spanning k-regular subgraph is a k-factor.

A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let $G$ be a graph on even $n$ vertices and $\lambda _{1}>\lambda _{2}>\ldots >\lambda _{\frac {n}{2}}>0$ be ${\frac {n}{2}}$ distinct nonzero purely imaginary numbers. Then $G$ has a perfect matching if and only if there is a real skew-symmetric matrix $A$ with graph $G$ and eigenvalues $\pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{\frac {n}{2}}$ .^[2] Note that the (simple) graph of a real symmetric or skew-symmetric matrix $A$ of order $n$ has $n$ vertices and edges given by the nonzero off-diagonal entries of $A$ .

Computation

Deciding whether a graph admits a perfect matching can be done in polynomial time, using any algorithm for finding a maximum cardinality matching.

However, counting the number of perfect matchings, even in bipartite graphs, is #P-complete. This is because computing the permanent of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its biadjacency matrix.

A remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm.

The number of perfect matchings in a complete graph K_n (with n even) is given by the double factorial: $(n-1)!!$ ^[3]

Connection to Graph Coloring

An edge-colored graph can induce a number of (not necessarily proper) vertex colorings equal to the number of perfect matchings, as every vertex is covered exactly once in each matching. This property has been investigated in quantum physics ^[4] and computational complexity theory.^[5]

Perfect matching polytope

The perfect matching polytope of a graph is a polytope in R^|E| in which each corner is an incidence vector of a perfect matching.

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ .

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In mathematics, Hall's marriage theorem, proved by Philip Hall, is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

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 matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In graph theory, a maximally matchable edge in a graph is an edge that is included in at least one maximum-cardinality matching in the graph. An alternative term is allowed edge.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

References

↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
↑ Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004
↑ Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv: 0906.1317 , Bibcode:2009arXiv0906.1317C .
↑ Mario Krenn, Xuemei Gu, Anton Zeilinger, Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings, Phys. Rev. Lett. 119, 240403 – Published 15 December 2017
↑ Moshe Y. Vardi, Zhiwei Zhang, Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints, arXiv:2301.09833 [cs.AI], IJCAI'23
↑ Wang, Xiumei; Shang, Weiping; Yuan, Jinjiang (2015-09-01). "On Graphs with a Unique Perfect Matching". Graphs and Combinatorics. 31 (5): 1765–1777. doi:10.1007/s00373-014-1463-8. ISSN 1435-5914.
↑ Hoang, Thanh Minh; Mahajan, Meena; Thierauf, Thomas (2006). Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). "On the Bipartite Unique Perfect Matching Problem". Automata, Languages and Programming. Berlin, Heidelberg: Springer: 453–464. doi:10.1007/11786986_40. ISBN 978-3-540-35905-0.
↑ Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (1985). Maheshwari, S. N. (ed.). "NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching". Foundations of Software Technology and Theoretical Computer Science. Berlin, Heidelberg: Springer: 496–503. doi:10.1007/3-540-16042-6_28. ISBN 978-3-540-39722-9.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.

[:1-2] Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004

[:2-3] Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv: 0906.1317 , Bibcode:2009arXiv0906.1317C .

[4] Mario Krenn, Xuemei Gu, Anton Zeilinger, Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings, Phys. Rev. Lett. 119, 240403 – Published 15 December 2017

[5] Moshe Y. Vardi, Zhiwei Zhang, Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints, arXiv:2301.09833 [cs.AI], IJCAI'23

[6] Wang, Xiumei; Shang, Weiping; Yuan, Jinjiang (2015-09-01). "On Graphs with a Unique Perfect Matching". Graphs and Combinatorics. 31 (5): 1765–1777. doi:10.1007/s00373-014-1463-8. ISSN 1435-5914.

[7] Hoang, Thanh Minh; Mahajan, Meena; Thierauf, Thomas (2006). Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). "On the Bipartite Unique Perfect Matching Problem". Automata, Languages and Programming. Berlin, Heidelberg: Springer: 453–464. doi:10.1007/11786986_40. ISBN 978-3-540-35905-0.

[8] Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (1985). Maheshwari, S. N. (ed.). "NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching". Foundations of Software Technology and Theoretical Computer Science. Berlin, Heidelberg: Springer: 496–503. doi:10.1007/3-540-16042-6_28. ISBN 978-3-540-39722-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]