主題
Search

獨立數

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

圖的（上）頂點獨立數，也稱為 1-填充數、填充數或穩定性數 (Acín et al. 2016)，通常簡稱為“獨立數”，是最大獨立頂點集的基數，即最大獨立頂點集（與最大極大獨立頂點集的大小相同）的大小。獨立數最常用的符號是 alpha(G)，但也可能寫成 beta(G)（例如，Burger et al. 1997）或 beta_0(G)（例如，Bollobás 1981）。

圖的獨立數等於該圖的獨立多項式中的最大指數。

下獨立數 i(G) 可以類似地定義為 G 中最小極大獨立頂點集的大小 (Burger et al. 1997)。

下冗餘數 ir(G)、下支配數 gamma(G)、下獨立數 i(G)、上獨立數 alpha(G)、上支配數 Gamma(G) 和 上冗餘數 IR(G) 滿足以下不等式鏈

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)
(1)

(Burger et al. 1997)。

圖 G 的獨立數與其頂點數的比率稱為 G 的獨立比率 (Bollobás 1981)。

圖 G 的獨立數等於補圖的團數，

alpha(G)=omega(G^_).
(2)

對於 n>1 個頂點且頂點度為 k 和最小圖特徵值為 s 的連通正則圖 G，

alpha<=(n(-s))/(k-s)
(3)

(A. E. Brouwer，私人通訊，2012 年 12 月 17 日)。

對於r，圖半徑，

alpha>=r
(4)

(DeLa Vina 和 Waller 2002)。Lovasz (1979, p. 55) 表明，當 rho 是路徑覆蓋數時，

alpha>=rho,
(5)

僅對於完全圖等式成立 (DeLa Vina 和 Waller 2002)。

Willis (2011) 給出了圖的獨立數的若干界限。

圖 G 的匹配數 nu(G) 等於其線圖 L(G) 的獨立數 alpha(L(G))。

根據定義，

alpha(G)+tau(G)=|G|,
(6)

其中 tau(G) 是 G 的頂點覆蓋數，n=|G| 是其頂點數 (West 2000)。

具有頂點集 V 和 邊集 E 的圖 G 的獨立數可以定義為整數規劃的結果

alpha(G)=max_(w_i+w_j<=1 for e_(ij) in E; w_i in {0,1})sum_(v in V)w_i
(7)

其中 w_i=w(v_i) 是第 i 個頂點上的權重。將此條件放寬為允許 w_i in [0,1] 得到分數獨立數 alpha^*(G)。

許多命名圖的預計算獨立數可以在 Wolfram 語言中使用以下命令獲得GraphData[graph,"IndependenceNumber"].

下面總結了某些圖類的已知值。

圖 Galpha(G)OEIS值
交錯群圖 AG_nA0000001, 1, 4, 20, 120, ...
n-Andrásfai 圖 (n>=3)nA0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-反稜柱圖 (n>=3)|_2n/3_|A0045232, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ...
n-阿波羅尼安網路3^(n-1)A0002441, 3, 9, 27, 81, 243, 729, 2187, ...
完全二部圖 K_(n,n)nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
完全圖 K_n1A0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
完全三部圖 K_(n,n,n)nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
圈圖 C_n (n>=3)|_n/2_|A0045261, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ...
空圖 K^__nnA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-摺疊立方體圖 (n>=2)2^(n-2)-1/4(1-(-1)^n)(n-1; (n-1)/2)A0586221, 1, 4, 5, 16, 22, 64, 93, 256, ...
網格圖 P_n square P_n[n^2/2]A0009821, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
網格圖 P_n square P_n square P_n[n^3/2]A0364861, 4, 14, 32, 63, 108, 172, 256, 365, 500, ...
n-半立方體圖A0058641, 1, 4, 5, 16, 22, 64, 93, 256, ...
n-漢諾塔圖3^(n-1)A0002441, 3, 9, 27, 81, 243, 729, 2187, ...
超立方體圖 Q_n2^(n-1)A0000791, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
n-Keller 圖{4 for n=1; 5 for n=2; 2^n otherwiseA2589354, 5, 8, 16, 32, 64, 128, 256, 512, ...
(n,n)-國王圖 (n>=2)|_(n+1)/2_|^2A0087941, 4, 4, 9, 9, 16, 16, 25, 25
(n,n)-騎士圖 (n>=2){4 for n=2; (1+(-1)^(n+1)+2n^2)/4 otherwiseA0309784, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
克內澤爾圖 K(n,k)(n-1; k-1)
n-Mycielski 圖{1 for n=1,2; 3·2^(n-3)-1 otherwiseA2665501, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ...
莫比烏斯梯子圖 M_n (n>=3)2[n/2]-1A1096133, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ...
奇圖 O_n{1 for n=1; (2n-2; n-2) otherwiseA0000001, 1, 4, 15, 56, 210, 792, 3003, 11440, ...
n-平底鍋圖1+|_n/2_|A0000002, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ...
路徑圖 P_n[n/2]A0045261, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...
稜柱圖 Y_n (n>=3)2|_n/2_|A0529282, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
n-謝爾賓斯基地毯圖4, 32, 256, ...
n-謝爾賓斯基墊片圖1, 3, 6, 15, 42, ...
星圖 S_n{1 for n=1; n-1 otherwiseA0283101, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
三角形圖 T_n (n>=2)|_n/2_|A0045261, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...
n-網狀圖 (n>=3)1/4[6n+(-1)^n-1]/4A0327664, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ...
輪圖 W_n|_(n-1)/2_|A0045261, 2, 2, 3, 3, 4, 4, 5, 5, ...

另請參閱

團數, 分數獨立數, 獨立多項式, 獨立比率, 獨立集, 下獨立數, 匹配數, 最大獨立頂點集, 最小頂點覆蓋, Shannon 容量, 頂點覆蓋

使用 探索

參考文獻

Acín, A.; Duan, R.; Roberson, D. E.; Belén Sainz, A.; 和 Winter, A. "a New Property of the Lovász Number and Duality Relations Between Graph Parameters." 2016 年 2 月 5 日。 https://arxiv.org/abs/1505.01265.Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.Burger, A. P.; Cockayne, E. J.; 和 Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Cockayne, E. J. 和 Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).DeLa Vina, E. 和 Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.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.Sloane, N. J. A. 序列 A000012/M0003, A000027/M0472, A000079/M1129, A000244/M2807, A000982/M1348, A004523, A004526, A005864/M1111, A008794, A028310, A030978, A032766, A036486, A052928, A058622, A109613, A258935, 和 A266550 West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.Willis, W. "Bounds for the Independence Number of a Graph." 碩士論文。Richmond, VA: Virginia Commonwealth University, 2011.

在 中被引用

獨立數

請引用為

Weisstein, Eric W. "Independence Number." 來自 --一個 資源。 https://mathworld.tw/IndependenceNumber.html

主題分類