主题
Search

独立顶点集

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook
IndependentSet

图 graph G 的一个独立顶点集，也称为稳定集，是顶点的一个子集，使得该子集中没有两个顶点代表图 G 的一条边。上图显示了几个图（轮图 W_8、效用图 K_(3,3)、彼得森图 和 弗鲁克特图）的由两个子集组成的独立集。

任何独立顶点集都是一个非冗余集（Burger et al. 1997, Mynhardt and Roux 2020）。

多项式的系数给出图 G 中每个基数的独立顶点集的数量，该多项式被称为其独立多项式。

一组顶点是一个独立顶点集，当且仅当它的补集形成一个顶点覆盖（Skiena 1990，p. 218）。因此，图中顶点覆盖和独立顶点集的计数是相同的。

空集显然是一个独立顶点集，因为它不包含任何顶点，因此也没有边端点。

最大独立顶点集是一个图中包含给定图的最大可能顶点数的独立顶点集，并且该集合的基数称为图的独立数。

通过添加一个顶点而无法扩大到另一个独立顶点集的独立顶点集称为极大独立顶点集。

在 Wolfram Language 中，命令FindIndependentVertexSet[g][[1]] 可以用来查找一个最大独立顶点集，并且FindIndependentVertexSet[g,Length /@ FindIndependentVertexSet[g],All] 用来查找所有最大独立顶点集。类似地，FindIndependentVertexSet[g,Infinity] 可以用来查找一个极大独立顶点集，并且FindIndependentVertexSet[g,Infinity, All] 用来查找所有独立顶点集。要在 Wolfram Language 中查找所有独立顶点集，枚举所有顶点子集 s 并选择那些满足IndependentVertexSetQ[g, s] 为真的子集。

下表总结了一些图族的独立顶点集计数。

图族OEIS独立顶点集数量
反棱柱图，对于 n>=3A000000X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ...
n×n 主教图A201862X, 9, 70, 729, 9918, 167281, ...
n×n 黑主教图A000000X, X, X, 27, 114, 409, 2066, ...
n-折叠立方体图A000000X, 3, 5, 31, 393, ...
网格图 P_n square P_n，对于 n>=2A006506X, 7, 63, 1234, 55447, 5598861, ...
网格图 P_n square P_n square P_n，对于 n>=2A000000X, 35, 70633, ...
n-半立方体图A0000002, 3, 5, 13, 57, ...
n-汉诺塔图A0000004, 52, 108144, ...
超立方体图 Q_nA0276243, 7, 35, 743, 254475, 19768832143, ...
n×n 国王图A063443X, 5, 35, 314, 6427, ...
n×n 骑士图A141243X, 16, 94, 1365, 55213, ...
n-莫比乌斯阶梯A182143X, X, 15, 33, 83, 197, 479, 1153, 2787, ...
n-米切尔斯基图A0000002, 3, 11, 103, 7407, ...
奇图 O_nA0000002, 4, 76, ...
棱柱图 Y_n，对于 n>=3A051927X, X, 13, 35, 81, 199, 477, 1155, 2785, ...
n×n 女王图A0000002, 5, 18, 87, 462, ...
n×n 车图A0027202, 7, 34, 209, 1546, 13327, 130922, ...
n-谢尔宾斯基垫片图A0000004, 14, 440, ...
n-三角形图A000000X, 2, 4, 10, 26, 76, 232, 764, ...
n-网状图，对于 n>=3A000000X, X, 68, 304, 1232, 5168, 21408, ...
n×n 白主教图A000000X, X, X, 27, 87, 409, 1657, ...

许多图族对于独立顶点集的计数具有简单的闭合形式，如下表所示。这里，F_n 是斐波那契数，L_n 是卢卡斯数，L_n(x) 是拉盖尔多项式，phi 是黄金比例，并且 alpha、beta、gamma 是 x^3-x^2-2x-1 的根。

图族独立顶点集数量
安德拉斯法伊图2^(n-1)(3n-1)+1
反棱柱图alpha^n+beta^n+gamma^n
书图 S_(n+1) square P_23^n+2^(n+1)
鸡尾酒会图 K_(n×2)3n+1
完全二分图 K_(n,n)2^(n+1)-1
完全图 K_nn+1
完全三部图 K_(n,n,n)3·2^n-2
2n-交叉棱柱图2^(-n)[(7-sqrt(21))^n+(7+sqrt(21))^n]
环图 C_nL_n
空图 K^__n2^n
齿轮图2^n+(phi+1)^n+(phi+1)^(-n)
舵图2^n+(1-sqrt(3))^n+(1+sqrt(3))^n
梯形图1/2[(1-sqrt(2))^(n+1)+(1+sqrt(2))^(n+1)]
梯 rung 图 nP_23^n
莫比乌斯阶梯 M_n(-1)^(n+1)+(1-sqrt(2))^n+(1+sqrt(2),)^n
平底锅图F_(n+1)+L_n
路径图 P_nF_(n+2)
棱柱图 Y_n(-1)^n+(1-sqrt(2))^n+(1+sqrt(2))^n
n×n 车图n!L_n(-1)
星图 S_n2^(n-1)+1
太阳图2^(n-2)(n+4)
太阳花图 C_n circledot K_1(1-sqrt(3))^n+(1+sqrt(3))^n
轮图 W_nL_(n-1)+1

另请参阅

团, 不相交集, 边覆盖, 空集, 独立数, 独立多项式, 独立集, 极大独立顶点集, 最大独立边集, 最大独立集问题, 最大独立顶点集, 维恩图, 顶点覆盖

使用 Wolfram|Alpha 探索

参考文献

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.Hochbaum, D. S. (Ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing, p. 125, 1997.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.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.

参见

独立集

引用为

韦斯坦因，埃里克·W. "独立顶点集。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/IndependentVertexSet.html

主题分类