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

另請參閱

團, 不相交集, 邊覆蓋, 空集, 獨立數, 獨立多項式, 獨立集, 極大獨立頂點集, 最大獨立邊集, 最大獨立集問題, 最大獨立頂點集, 維恩圖, 頂點覆蓋

使用 探索

參考文獻

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. "獨立頂點集。" 來自 Web 資源。 https://mathworld.tw/IndependentVertexSet.html

主題分類