Matching
Encyclopedia
In the mathematical discipline of graph theory
, a matching or independent edge set in a graph
is a set of edges without common vertices
. It may also be an entire graph consisting of edges without common vertices.
G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.
A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched.
A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a proper subset of any other matching in graph G. In other words, 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 is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number
of a graph 
is the size of a maximum matching. Note that every maximum matching is maximal, but not every maximal matching is a maximum matching. The following figure shows examples of maximum matchings in three graphs.
A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident
to exactly one edge of the matching. Figure (b) above is an example of a perfect matching. 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,, that is, the size of a maximum matching is no larger than the size of a minimum edge cover.
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
.
Given a matching M,
One can prove that a matching is maximum if and only if it does not have any augmenting path. (This result is sometimes called Berge's lemma
.)
If A and B are two maximal matchings, then |A| ≤ 2|B| and |B| ≤ 2|A|. To see this, observe that each edge in A \ B can be adjacent to at most two edges in B \ A because B is a matching. Since each edge in B \ A is adjacent to an edge in A \ B by maximality, we see that
Further we get that
In particular, this shows that any maximal matching is a 2-approximation of a maximum matching and also a 2-approximation of a minimum maximal matching. This inequality is tight: for example, if G is a path with 3 edges and 4 nodes, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2.
of the number of k-edge matchings in a graph is called a matching polynomial. Let G be a graph and mk be the number of k-edge matchings. One matching polynomial of G is
Another definition gives the matching polynomial as
where n is the number of vertices in the graph. Each type has its uses; for more information see the article on matching polynomials.
s. Finding a maximum bipartite matching
(often called a maximum cardinality bipartite matching) in a bipartite graph
is perhaps the simplest problem. The augmenting path algorithm finds it by finding an augmenting path from each to 
and adding it to the matching if it exists. As each path can be found in 
time, the running time is 
. This solution is equivalent to adding a super source 
with edges to all vertices in 
, and a super sink 
with edges from all vertices in 
, and finding a maximal flow
from
to 
. All edges with flow from 
to 
then constitute a maximum matching. An improvement over this is the Hopcroft-Karp algorithm
, which runs in time. Another approach is based on the fast matrix multiplication
algorithm and gives
complexity, which is better in theory for sufficiently dense graph
s, but in practice the algorithm is slower.
In a weighted bipartite graph, each edge has an associated value. A maximum weighted bipartite matching is defined as a perfect matching where the sum of the values of the edges in the matching have a maximal value. If the graph is not complete bipartite, missing edges are inserted with value zero. Finding such a matching is known as the assignment problem
. It can be solved by using a modified shortest path search in the augmenting path algorithm. If the Bellman-Ford algorithm
is used, the running time becomes
, or the edge cost can be shifted with a potential to achieve 
running time with the Dijkstra algorithm and Fibonacci heap
. The remarkable Hungarian algorithm
solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. The original approach of this algorithm needs
running time, but it could be improved to 
time with extensive use of priority queues.
, is called the paths, trees, and flowers method or simply Edmonds's algorithm
, and uses bidirected edges
. A generalization of the same technique can also be used to find maximum independent sets in claw-free graphs. Edmonds' algorithm has subsequently been improved to run in time time, matching the time for bipartite maximum matching.
Another algorithm by Mucha and Sankowski, based on the fast matrix multiplication
algorithm, gives
complexity.
Note that a maximal matching with k edges is an edge dominating set
with k edges. Conversely, if we are given a minimum edge dominating set with k edges, we can construct a maximal matching with k edges in polynomial time. Therefore the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set. Both of these two optimisation problems are known to be NP-hard
; the decision versions of these problems are classical examples of NP-complete
problems. Both problems can be approximated
within factor 2 in polynomial time: simply find an arbitrary maximal matching M.
). However, 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
. There exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.
For the problem of determining the total number of matchings in a given graph, see Hosoya index
.
states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover
. Via this result, the minimum vertex cover, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs.
The marriage theorem
(or Hall's Theorem) provides a characterization of bipartite graphs which have a perfect matching and 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.
consists of a perfect matching of its carbon skeleton
, showing the locations of double bond
s in the chemical structure
. These structures are named after Friedrich August Kekulé von Stradonitz
, who showed that benzene
(in graph theoretical terms, a 6-vertex cycle) can be given such a structure.
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a matching or independent edge set in a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
is a set of edges without common vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
. It may also be an entire graph consisting of edges without common vertices.
Definition
Given a graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.
A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched.
A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a proper subset of any other matching in graph G. In other words, 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 is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number
of a graph is the size of a maximum matching. Note that every maximum matching is maximal, but not every maximal matching is a maximum matching. The following figure shows examples of maximum matchings in three graphs.A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident
Incidence (geometry)
In geometry, the relations of incidence are those such as 'lies on' between points and lines , and 'intersects' . That is, they are the binary relations describing how subsets meet...
to exactly one edge of the matching. Figure (b) above is an example of a perfect matching. 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
Edge cover
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set.In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size...
. Thus,, that is, the size of a maximum matching is no larger than the size of a minimum edge cover.
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
Factor-critical graph
In graph theory, a mathematical discipline, a factor-critical graph is a graph with vertices in which every subgraph of vertices has a perfect matching, a subset of its edges such that each of the vertices is the endpoint of exactly one of the edges in the subset.A matching that covers all but...
.
Given a matching M,
- an alternating path is a path in which the edges belong alternatively to the matching and not to the matching.
- an augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.
One can prove that a matching is maximum if and only if it does not have any augmenting path. (This result is sometimes called Berge's lemma
Berge's lemma
In graph theory, Berge's lemma states that a matching M in a graph G is maximum if and only if there is no augmenting path with M.It was proven by French mathematician Claude Berge in 1957.- Proof...
.)
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.If A and B are two maximal matchings, then |A| ≤ 2|B| and |B| ≤ 2|A|. To see this, observe that each edge in A \ B can be adjacent to at most two edges in B \ A because B is a matching. Since each edge in B \ A is adjacent to an edge in A \ B by maximality, we see that
Further we get that
In particular, this shows that any maximal matching is a 2-approximation of a maximum matching and also a 2-approximation of a minimum maximal matching. This inequality is tight: for example, if G is a path with 3 edges and 4 nodes, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2.
Matching polynomials
A generating functionGenerating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
of the number of k-edge matchings in a graph is called a matching polynomial. Let G be a graph and mk be the number of k-edge matchings. One matching polynomial of G is
Another definition gives the matching polynomial as
where n is the number of vertices in the graph. Each type has its uses; for more information see the article on matching polynomials.
Maximum matchings in bipartite graphs
Matching problems are often concerned with bipartite graphBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
s. Finding a maximum bipartite matching
(often called a maximum cardinality bipartite matching) in a bipartite graph
is perhaps the simplest problem. The augmenting path algorithm finds it by finding an augmenting path from each to and adding it to the matching if it exists. As each path can be found in time, the running time is . This solution is equivalent to adding a super source with edges to all vertices in , and a super sink with edges from all vertices in , and finding a maximal flowMaximum flow problem
In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....
from
to . All edges with flow from to then constitute a maximum matching. An improvement over this is the Hopcroft-Karp algorithmHopcroft-Karp algorithm
In computer science, the Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching – a set of as many edges as possible with the property that no two edges share an endpoint...
, which runs in time. Another approach is based on the fast matrix multiplication
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
algorithm and gives
complexity, which is better in theory for sufficiently dense graphDense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
s, but in practice the algorithm is slower.
In a weighted bipartite graph, each edge has an associated value. A maximum weighted bipartite matching is defined as a perfect matching where the sum of the values of the edges in the matching have a maximal value. If the graph is not complete bipartite, missing edges are inserted with value zero. Finding such a matching is known as the assignment problem
Assignment problem
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...
. It can be solved by using a modified shortest path search in the augmenting path algorithm. If the Bellman-Ford algorithm
Bellman-Ford algorithm
The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem....
is used, the running time becomes
, or the edge cost can be shifted with a potential to achieve running time with the Dijkstra algorithm and Fibonacci heapFibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
. The remarkable Hungarian algorithm
Hungarian algorithm
The Hungarian method is a combinatorial optimization algorithm which solves the assignment problem in polynomial time and which anticipated later primal-dual methods...
solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. The original approach of this algorithm needs
running time, but it could be improved to time with extensive use of priority queues.Maximum matchings
There is a polynomial time algorithm to find a maximum matching or a maximum weight matching in a graph that is not bipartite; it is due to Jack EdmondsJack Edmonds
Jack R. Edmonds is a mathematician, regarded as one of the most important contributors to the field of combinatorial optimization...
, is called the paths, trees, and flowers method or simply Edmonds's algorithm
Edmonds's matching algorithm
Edmonds's matching algorithmis an algorithm in graph theory for constructing maximum matchings on graphs. The algorithm was discovered by Jack Edmonds in 1965. Given a general graph G = , the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is...
, and uses bidirected edges
Bidirected graph
In the mathematical domain of graph theory, a bidirected graph is a graph in which each edge is given an independent orientation at each end...
. A generalization of the same technique can also be used to find maximum independent sets in claw-free graphs. Edmonds' algorithm has subsequently been improved to run in time time, matching the time for bipartite maximum matching.
Another algorithm by Mucha and Sankowski, based on the fast matrix multiplication
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
algorithm, gives
complexity.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.Note that a maximal matching with k edges is an edge dominating set
Edge dominating set
In graph theory, an edge dominating set for a graph G = is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set...
with k edges. Conversely, if we are given a minimum edge dominating set with k edges, we can construct a maximal matching with k edges in polynomial time. Therefore the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set. Both of these two optimisation problems are known to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
; the decision versions of these problems are classical examples of NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems. Both problems can be approximated
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
within factor 2 in polynomial time: simply find an arbitrary maximal matching M.
Counting problems
The problem of determining the number of perfect matchings in a given graph is #P Complete (see PermanentPermanent
The permanent of a square matrix in linear algebra, is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix...
). However, a remarkable theorem of Kasteleyn
Pieter Kasteleyn
Pieter Willem Kasteleyn was a Dutch physicist famous for his contributions to the field of Statistical Mechanics.-Biography:...
states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm
FKT algorithm
The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. Counting the number of matchings, even for planar graphs, is also #P-complete...
. There exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.
For the problem of determining the total number of matchings in a given graph, see Hosoya index
Hosoya index
The Hosoya index, also known as the Z index, of a graph is the total number of matchings in it. The Hosoya index is always at least one, because the empty set of edges is counted as a matching for this purpose. Equivalently, the Hosoya index is the number of non-empty matchings plus...
.
Characterizations and Notes
König's theoremKönig's theorem (graph theory)
In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...
states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
. Via this result, the minimum vertex cover, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs.
The marriage theorem
Marriage theorem
In mathematics, Hall's marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets...
(or Hall's Theorem) provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem
Tutte theorem
In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings...
provides a characterization for arbitrary graphs.
A perfect matching is a spanning 1-regular
Regular graph
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 vertex are equal to each other...
subgraph, a.k.a. a 1-factor. In general, a spanning k-regular subgraph is a k-factor.
Applications
A Kekulé structure of an aromatic compoundAromaticity
In organic chemistry, Aromaticity is a chemical property in which a conjugated ring of unsaturated bonds, lone pairs, or empty orbitals exhibit a stabilization stronger than would be expected by the stabilization of conjugation alone. The earliest use of the term was in an article by August...
consists of a perfect matching of its carbon skeleton
Skeletal formula
The skeletal formula of an organic compound is a shorthand representation of its molecular structure, developed by the organic chemist, Friedrich August Kekulé von Stradonitz. Skeletal formulae are ubiquitous in organic chemistry, because they are relatively quick and simple to draw. Carbon and...
, showing the locations of double bond
Double bond
A double bond in chemistry is a chemical bond between two chemical elements involving four bonding electrons instead of the usual two. The most common double bond, that between two carbon atoms, can be found in alkenes. Many types of double bonds between two different elements exist, for example in...
s in the chemical structure
Chemical structure
A chemical structure includes molecular geometry, electronic structure and crystal structure of molecules. Molecular geometry refers to the spatial arrangement of atoms in a molecule and the chemical bonds that hold the atoms together. Molecular geometry can range from the very simple, such as...
. These structures are named after Friedrich August Kekulé von Stradonitz
Friedrich August Kekulé von Stradonitz
Friedrich August Kekule von Stradonitz was a German organic chemist. From the 1850s until his death, Kekule was one of the most prominent chemists in Europe, especially in theoretical chemistry...
, who showed that benzene
Benzene
Benzene is an organic chemical compound. It is composed of 6 carbon atoms in a ring, with 1 hydrogen atom attached to each carbon atom, with the molecular formula C6H6....
(in graph theoretical terms, a 6-vertex cycle) can be given such a structure.
The Hosoya index
Hosoya index
The Hosoya index, also known as the Z index, of a graph is the total number of matchings in it. The Hosoya index is always at least one, because the empty set of edges is counted as a matching for this purpose. Equivalently, the Hosoya index is the number of non-empty matchings plus...
is the number of non-empty matchings plus one; it is used in computational chemistry
Computational chemistry
Computational chemistry is a branch of chemistry that uses principles of computer science to assist in solving chemical problems. It uses the results of theoretical chemistry, incorporated into efficient computer programs, to calculate the structures and properties of molecules and solids...
and mathematical chemistry
Mathematical chemistry
Mathematical chemistry is the area of research engaged in novel applications of mathematics to chemistry; it concerns itself principally with the mathematical modeling of chemical phenomena...
investigations for organic compounds.
See also
- Edge coloringEdge coloringIn graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent 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...
- Vertex independent set
- Dulmage–Mendelsohn decomposition
- Stable matching
- Skew-symmetric graphSkew-symmetric graphIn graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges. The isomorphism is required to be an involution without any fixed points....