主题
Search

顶点覆盖

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

设 S 是有限集 X 的子集集合。 Y 是 X 的一个子集，它与 S 的每个成员相交，称为顶点覆盖，或命中集。

VertexCover

图 G 的顶点覆盖也可以更简单地被认为是 S 的顶点集， G 使得 G 的每条边至少有一个端点是 S 的成员。 因此，图的顶点集始终是顶点覆盖。 给定图 G 的最小可能顶点覆盖称为最小顶点覆盖 (Skiena 1990, p. 218)，其大小称为顶点覆盖数，表示为 tau(G)。 上面显示了一些图的顶点覆盖，以红色着色表示。 在完全k-部图中，顶点覆盖包含来自至少 k-1 个阶段的顶点。

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

对于给定的图，具有最小可能顶点数的顶点覆盖称为最小顶点覆盖。 可以在Wolfram 语言中使用以下命令找到图的最小顶点覆盖FindVertexCover[g].

可以使用以下命令在Wolfram 语言中测试图是否为给定图的顶点覆盖VertexCoverQ[g]. 可以使用以下命令查找许多命名图的预计算顶点覆盖GraphData[graph,"VertexCovers"].

下表总结了一些图族的顶点覆盖计数。

图族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-Mycielski 图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-Sierpiński 垫片图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 的根。

图族顶点覆盖的数量
Andrásfai 图2^(n-1)(3n-1)+1
反棱柱图alpha^n+beta^n+gamma^n
书图 S_(n+1)P_23^n+2^(n+1)
鸡尾酒会图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)]
梯子横档图 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 探索

参考文献

Pemmaraju, S. 和 Skiena, S. "最小顶点覆盖。" §7.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 317, 2003.Skiena, S. "最小顶点覆盖。" §5.6.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 218, 1990.Skiena, S. S. "顶点覆盖。" §8.5.3 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 317-318, 1997.

在 Wolfram|Alpha 中被引用

顶点覆盖

引用为

Weisstein, Eric W. "顶点覆盖。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/VertexCover.html

主题分类