Matching Number
المؤلف:
West, D. B
المصدر:
Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
الجزء والصفحة:
...
26-4-2022
1966
Matching Number
The (upper) matching number 
of graph 
, sometimes known as the edge independence number, is the size of a maximum independent edge set. Equivalently, it is the degree of the matching-generating polynomial
 |
(1)
|
where 
is the number of 
-matchings of a graph 
. The notations 
, 
, or 
are sometimes also used.
The matching number is also the size of a largest maximal independent edge set, while the size of a smallest maximal independent edge set is called the lower matching number.
satisfies
 |
(2)
|
where 
is the vertex count of 
, 
is the floor function. Equality occurs only for a perfect matching, and graph 
has a perfect matching iff
 |
(3)
|
where 
is the vertex count of 
.
The matching number 
of a graph 
is equal to the independence number 
of its line graph 
.
The König-Egeváry theorem states that the matching number equals the vertex cover number (i.e., size of the smallest minimum vertex cover) are equal for a bipartite graph.
If a graph 
has no isolated points, then
 |
(4)
|
where 
is the matching number, 
is the size of a minimum edge cover, and 
is the vertex count of 
(West 2000).
Precomputed matching numbers for many named graphs are available in the Wolfram Language using GraphData[graph, "MatchingNumber"].
REFERENCES
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
