主题
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]] 将找到所有最大独立顶点集。

另请参阅

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

使用 Wolfram|Alpha 探索

参考文献

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." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MaximumIndependentVertexSet.html

学科分类