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

另请参阅

团覆盖, 团覆盖数, 团数, 团多项式, 下团数, 极大团, 最大团

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

团 (Clique)

引用为

Weisstein, Eric W. "团 (Clique)." 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/Clique.html

主题分类