Read More
Date: 18-5-2022
1382
Date: 3-3-2022
1820
Date: 1-4-2022
1668
|
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"].
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|