主题
Search

最大独立顶点集

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

图 graph G 的独立顶点集是顶点的子集，使得子集中没有两个顶点表示图 G 的边。给定图的顶点覆盖，所有不在覆盖中的顶点定义了一个独立顶点集（Skiena 1990, p. 218）。最大独立顶点集是对于给定图，包含可能的最大顶点数的独立顶点集。

最大独立顶点集不等同于极大独立顶点集，极大独立顶点集只是一个不能扩展到更大独立顶点集的独立顶点集。每个最大独立顶点集也是一个独立顶点集，但反之不然。

图的独立数是最大独立集的基数。

最大独立顶点集对应于最小顶点覆盖的补集。

MaximumIndependentSet

在给定的图 graph g 中，可以使用 Wolfram 语言找到最大独立顶点集，方法是使用FindIndependentVertexSet[g][[1]]。命令Sort[FindIndependentVertexSet[g,Length /@ FindIndependentVertexSet[g], All]] 将找到所有最大独立顶点集。

另请参阅

独立数, 独立集, 独立顶点集, 极大独立顶点集, 最大独立边集, 最大独立集问题, 最小顶点覆盖, 顶点覆盖

使用 探索

参考文献

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 载于 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 载于 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

请引用为

Weisstein, Eric W. "Maximum Independent Vertex Set." 来自 Web 资源。 https://mathworld.net.cn/MaximumIndependentVertexSet.html

学科分类