主題
Search

團 (Clique)

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
Clique

圖 G 的團是 G 的完全子圖，而可能的最大尺寸的團被稱為最大團（其大小被稱為（上）團數 omega(G)）。然而，需要注意的是，最大團通常簡稱為“團”（例如，Harary 1994）。極大團是不能透過包含一個或多個相鄰頂點來擴充套件的團，這意味著它不是更大團的子集。因此，最大團是極大團（但反之不一定成立）。

團出現在圖論和組合數學的許多領域，包括圖著色和糾錯碼理論。

大小為 k 的團被稱為 k-團（儘管這個術語有時也用於表示一組頂點，這些頂點彼此之間的距離不大於 k 的最大集合）。0-團對應於空集（0 個頂點的集合），1-團對應於頂點，2-團對應於邊，3-團對應於 3-圈。

團多項式是圖 G 定義為

C_G(x)=sum_(k=0)^(omega(G))c_kx^k,

其中 c_k 是大小為 k 的團的數量，其中 c_0=1，c_1=|G| 等於 G 的頂點數，c_2=m(G) 等於 G 的邊數，等等。

在 Wolfram 語言中，命令FindClique[g][[1]] 可以用來找到一個最大團，以及FindClique[g,Length /@ FindClique[g],All] 來找到所有最大團。類似地，FindClique[g,Infinity] 可以用來找到一個極大團，以及FindClique[g,Infinity, All] 來找到所有極大團。要找到所有團，列舉所有頂點子集 s 並選擇那些滿足以下條件的子集CompleteGraphQ[g, s] 為真。

一般而言，FindClique[g, n] 可以用來找到一個包含至少 n 個頂點的極大團，FindClique[g, n,All] 來找到所有這樣的團，FindClique[g, {n}] 來找到一個恰好包含 n 個頂點的團，以及FindClique[g, {n},All] 來找到所有這樣的團。

對於各種圖族，團的數量（等於在 x=1 處評估的團多項式）總結在下表中，其中團多項式中初始的 1 代表的平凡 0-團包含在每個計數中。

圖族OEIS團的數量
交錯群圖A308599X, 2, 8, 45, 301, 2281, ...
Andrásfai 圖A1150674, 11, 21, 34, 50, 69, 91, ...
n×n 羚羊圖A3086002, 5, 10, 17, 34, 61, 98, ...
反稜柱圖A017077X, X, 27, 33, 41, 49, 57, 65, ...
阿波羅網路A20524816, 40, 112, 328, 976, 2920, ...
啞鈴圖A000079X, X, 16, 32, 64, 128, 256, 512, ...
n×n 主教圖A1831562, 7, 22, 59, 142, 319, ...
n×n 黑主教圖A2959092, 4, 14, 30, 82, 160, 386, ...
書圖 S_(n+1) square P_2A0168979, 14, 19, 24, 29, 34, 39, 44, ...
Bruhat 圖A1391492, 4, 13, 61, 361, 2521, 20161, ...
蜈蚣圖A0085864, 8, 12, 16, 20, 24, 28, 32, 36, ...
雞尾酒會圖 K_(n×2)A0002443, 9, 27, 81, 243, 729, 2187, ...
完全圖 K_nA0000792, 4, 8, 16, 32, 64, 128, 256, ...
完全二部圖 K_(n,n)A0002904, 9, 16, 25, 36, 49, 64, 81, 100, ...
完全三部圖 K_(n,n,n)A0005788, 27, 64, 125, 216, 343, 512, ...
2n-交叉稜柱圖A017281X, 21, 31, 41, 51, 61, 71, ...
冠狀圖 K_2 square K_n^_A002061X, X, 13, 21, 31, 43, 57, 73, 91, ...
立方體連線環圖A295926X, X, 69, 161, 401, 961, 2241, 5121, ...
環圖 C_nA308602X, X, 8, 9, 11, 13, 15, 17, 19, ...
雙稜錐圖A308603X, X, 24, 27, 33, 39, 45, 51, 57, 63, ...
空圖 K^__nA0000272, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
斐波那契立方圖A2919164, 6, 11, 19, 34, 60, 106, 186, ...
n×n 五跳棋圖A308604X, 4, 16, 25, 57, 129, 289, 641, 1409, ...
摺疊立方圖A2959213, 15, 24, 56, ...
齒輪圖A016873X, X, 17, 22, 27, 32, 37, 42, 47, 52, ...
網格圖 P_n square P_nA0561052, 9, 22, 41, 66, 97, 134, 177, 226, 281, ...
網格圖 P_n square P_n square P_nA2959072, 21, 82, 209, 426, 757, 1226, 1857, ...
半立方圖A2959222, 4, 16, 81, 393, 1777, ...
河內圖A2959118, 25, 76, 229, 688, ...
舵圖A016933X, X, 22, 26, 32, 38, 44, 50, 56, ...
超立方體圖 Q_nA1327504, 9, 21, 49, 113, 257, 577, 1281, 2817, ...
Keller 圖A2959025, 57, 14833, 2290312801, ...
n×n 國王圖A2959062, 16, 50, 104, 178, 272, 386, ...
n×n 騎士圖A2959052, 5, 18, 41, 74, 117, 170, 233, 306, 389, ...
梯子圖 P_2 square P_nA0168974, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, ...
梯子橫檔圖 nP_2A0167774, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, ...
Menger 海綿圖A29220945, 1073, 22977, ...
莫比烏斯梯子 M_nA016861X, X, 16, 21, 26, 31, 36, 41, 46, 51, ...
Mycielski 圖A1991092, 4, 11, 32, 95, 284, 851, 2552, 7655, ...
奇圖 O_nA2959342, 8, 26, 106, 442, 1849, 7723, ...
平底鍋圖A005408X, X, 10, 11, 13, 15, 17, 19, 21, 23, ...
路徑圖 P_nA0058432, 4, 6, 8, 10, 12, 14, 16, 18, 20, ...
路徑補圖 P^__nA0000452, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
置換星圖A1391492, 4, 13, 61, 361, 2521, ...
多邊形對角線交點圖A300524X, X, 8, 18, 41, 80, 169, 250, ...
稜柱圖 K_2 square C_nA016861X, X, 18, 21, 26, 31, 36, 41, 46, 51, ...
n×n 皇后圖A2959032, 16, 94, 293, 742, 1642, 3458, 7087, ...
車圖 K_n square K_nA2889582, 9, 34, 105, 286, 721, 1730, ...
車補圖 K_n square K_n^_A0027202, 7, 34, 209, 1546, 13327, 130922, ...
謝爾賓斯基地毯圖A29593217, 153, 1289, 10521, ...
謝爾賓斯基墊片圖A2959338, 20, 55, 160, 475, ...
謝爾賓斯基四面體圖A2925376, 59, 227, 899, 3587, 14339, ...
星圖 S_nA0058432, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, ...
太陽圖A295904X, X, 20, 32, 52, 88, 156, 288, 548, ...
小日冕圖 C_n circledot K_1A016813X, X, 14, 17, 21, 25, 29, 33, 37, 41, 45, ...
四面體圖A289837X, X, X, X, X, 261, 757, 2003, 5035, ...
環面網格圖 C_n square C_nA056107X, X, 34, 49, 76, 109, 148, 193, ...
轉置圖A3086062, 4, 16, 97, 721, 6121, ...
三角圖A290056X, 2, 8, 27, 76, 192, 456, 1045, ...
三角形網格圖A2426588, 20, 38, 62, 92, 128, 170, 218, ...
三角形蛇形圖 TS_nA0167892, X, 8, X, 14, X, 20, X, 26, X, 32, X, ...
網狀圖A016993X, X, 24, 29, 36, 43, 50, 57, 64, 71, 78, ...
輪圖 W_nA308607X, X, X, 16, 18, 22, 26, 30, 34, 38, 42, 46, ...
n×n 白主教圖A295910X, 4, 9, 30, 61, 160, 301, 71, ...

下表總結了其中一些圖的閉合形式。

圖族團的數量
Andrásfai 圖1/2(n+2)(3n-1)
反稜柱圖{26 for n=3; 8n for n>=4
書圖 S_(n+1) square P_25n+3
雞尾酒會圖 K_(n×2)3^n-1
完全二部圖 K_(n,n)2^n-1
完全圖 K_nn(n+2)
完全三部圖 K_(n,n,n)n(n^2+3n+3)
2n-交叉稜柱圖10n
環圖 C_n{7 for n=3; 2n for n>=4
空圖 K^__nn
齒輪圖5n+11
舵圖{21 for n=3; 8n for n>=4
超立方體圖 Q_n2^(n-1)(n+2)
梯子圖5n-2
梯子橫檔圖 nP_23n
莫比烏斯梯子 M_n5(n+2)
平底鍋圖{9 for n=3; 2(n+1) for n>=4
路徑圖 P_n2n-1
稜柱圖 Y_n{17 for n=3; 5n for n>=4
星圖 S_n2n-1
太陽圖2^n+4n-1
小日冕圖 C_n circledot K_1{13 for n=3; 4n for n>=4
網狀圖{23 for n=3; 7n for n>=4
輪圖 W_n{15 for n=3; 4n-3 for n>=4

另請參閱

團覆蓋, 團覆蓋數, 團數, 團多項式, 下團數, 極大團, 最大團

使用 探索

參考文獻

Harary, F. 圖論。 Reading, MA: Addison-Wesley, 1994.Pemmaraju, S. 和 Skiena, S. 計算離散數學：Mathematica 中的組合學和圖論。 Cambridge, England: Cambridge University Press, pp. 247-248, 2003.Skiena, S. "最大團。" §5.6.1 在 實現離散數學：Mathematica 的組合學和圖論。 Reading, MA: Addison-Wesley, pp. 215 和 217-218, 1990.Skiena, S. S. "團和獨立集" 和 "團。" §6.2.3 和 8.5.1 在 演算法設計手冊。 New York: Springer-Verlag, pp. 144 和 312-314, 1997.

在 中被引用

團 (Clique)

引用為

Weisstein, Eric W. "團 (Clique)." 來自 --一個 資源。 https://mathworld.tw/Clique.html

主題分類