Read More
Date: 13-4-2022
1694
Date: 1-4-2022
2123
Date: 1-5-2022
1752
|
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 |
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.
|
|
"عادة ليلية" قد تكون المفتاح للوقاية من الخرف
|
|
|
|
|
ممتص الصدمات: طريقة عمله وأهميته وأبرز علامات تلفه
|
|
|
|
|
ندوات وأنشطة قرآنية مختلفة يقيمها المجمَع العلمي في محافظتي النجف وكربلاء
|
|
|