Maximum Independent Vertex Set
المؤلف:
Myrvold, W. and Fowler, P. W.
المصدر:
"Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85
الجزء والصفحة:
...
4-5-2022
1504
Maximum Independent Vertex Set
An independent vertex set of a graph 
is a subset of the vertices such that no two vertices in the subset represent an edge of 
. Given a vertex cover of a graph, all vertices not in the cover define a independent vertex set (Skiena 1990, p. 218). A maximum independent vertex set is an independent vertex set containing the largest possible number of vertices for a given graph.
A maximum independent vertex set is not equivalent to a maximal independent vertex set, which is simply an independent vertex set that cannot be extended to a larger independent vertex set. Every maximum independent vertex set is also an independent vertex set, but the converse is not true.
The independence number of a graph is the cardinality of the maximum independent set.
Maximum independent vertex sets correspond to the complements of minimum vertex covers.
A maximum independent vertex set in a given graph 
can be found in the Wolfram Language using FindIndependentVertexSet[g][[1]]. The command Sort[FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All]] will find all maximum independent vertex sets.
REFERENCES
Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.
Pemmaraju, S. and Skiena, S. "Maximum Independent Set." §7.5.3 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.
Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
