Minimum Vertex Cover
المؤلف:
Pemmaraju, S. and Skiena, S
المصدر:
"Minimum Vertex Cover." §7.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press
الجزء والصفحة:
...
26-4-2022
2346
Minimum Vertex Cover
A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph 
is known as the vertex cover number and is denoted 
.
Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily vice versa.
Finding a minimum vertex cover of a general graph is an NP-complete problem. However, for a bipartite graph, the König-Egeváry theorem allows a minimum vertex cover to be found in polynomial time.
A minimum vertex cover of a graph can be computed in the Wolfram Language using FindVertexCover[g]. There is currently no Wolfram Language function to compute all minimum vertex covers.
Minimum vertex covers correspond to the complements of maximum independent vertex sets.
REFERENCES
Pemmaraju, S. and Skiena, S. "Minimum Vertex Cover." §7.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 317, 2003.
Skiena, S. "Minimum Vertex Cover." §5.6.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 218, 1990.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
