Matching
المؤلف:
Lovász, L. and Plummer, M. D
المصدر:
Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.
الجزء والصفحة:
...
8-5-2022
2627
Matching
A matching, also called an independent edge set, on a graph 
is a set of edges of 
such that no two sets share a vertex in common.
It is not possible for a matching on a graph with 
nodes to exceed 
edges. When a matching with 
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 
and is denoted 
.
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 
-matchings of a graph with 
vertices be denoted 
. Then 
(since the empty set consisting of no edges is always a 0-matching) and 
, where 
is the edge count of 
.
The matching polynomial is defined by
and the matching-generating polynomial by
The numbers of distinct 
-matchings for various specials classes of graphs are summarized in the following table, where 
denotes a factorial, 
is a double factorial, 
is a binomial coefficient, and 
is the discrete delta function.
| graph |
 |
complete graph  |
 |
complete bipartite graph  |
 |
cycle graph  |
 |
empty graph  |
 |
path graph  |
 |
REFERENCES
Hopcroft, J. and Karp, R. "An 
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
