主題
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

另請參閱

團, 邊覆蓋, 匈牙利最大匹配演算法, 獨立集, 最大獨立頂點集, 最小頂點覆蓋, 頂點覆蓋數, 頂點覆蓋多項式

使用 探索

參考文獻

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.

在 中被引用

頂點覆蓋

引用為

Weisstein, Eric W. "頂點覆蓋。" 來自 網路資源。 https://mathworld.tw/VertexCover.html

主題分類