团 (图论)

在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。团是图论中的基本概念之一，用在很多数学问题以及图的构造上。计算机科学中也有对它的研究，尽管在一个图中寻找给定大小的团达到了NP完全的难度，人们还是研究过很多寻找团的算法。

虽然对完全子图的研究可以追溯到Erdős & Szekeres (1935)中拉姆齐理论对图理论的重组^[1]，“团”这一术语本身其实源自 Luce & Perry (1949)，那篇文章中社会网络的完全子图被用来模拟一“团”人，也就是一组两两相互认识的人。团在科学领域特别是在生物信息学中有许多其他应用。

定义

顶点集C被称为无向图 G=(V,E) 的团，如果C是顶点集V的子集(C⊆V)，而且任意两个C中的顶点都有边连接。另一种等价的说法是，由C诱导的子图是完全图 （有时也用“团”来指这样的子图）。

极大团是指增加任一顶点都不再符合团定义的团，也就是说，极大团不能被任何一个更大的团所包含。

最大团是一个图中顶点数最多的团。图G的团数（clique number）ω(G) 是指G中最大团的顶点数。图G的边团覆盖数（edge clique cover number）是指覆盖G中所有的边所需要的最少的团的数目。图G的二分维数（英语：Bipartite dimension）是指覆盖G中所有边所需要的最少的二分团的数目，其中二分团（biclique）就是完全二分子图 。而分团覆盖问题 （Clique cover problem）所关心的是用最少的团去覆盖G中所有的顶点。

独立集是刚好和团相反的概念，因为图G中的团和图G的补图中的独立集是一一对应的。

相关性质

• Cluster graph（英语：Cluster_graph）的连通分量为团。
• Block graph（英语：Block_graph）的2-连通分量（英语：Biconnected_component）为团。
• 弦图的点具有完美消去序（perfect elimination ordering），这种排序具有如下性质：对于所有的点${\displaystyle v}$，${\displaystyle N(v)}$中排序在${\displaystyle v}$后的点和${\displaystyle v}$共同构成一个团。
• Cograph（英语：Cograph）的所有导出子图具有如下性质：任意极大团与任意极大独立集（英语：Maximal_independent_set）有且仅有一个共同点。
• Interval graph（英语：Interval_graph）的极大团可以按照如下方式排序：对于任意点${\displaystyle v}$包含${\displaystyle v}$的团在排序中是连续的。
• 线图的边能被一些没有公共边的团所覆盖，并且每个点恰好属于两个团。
• 完美图（英语：Perfect_graph）的所有导出子图的团数等于色数。
• Split graph（英语：Split_graph）包含具有如下性质的团：对于图中每条边，至少包含一个顶点。
• Triangle-free graph（英语：Triangle-free_graph）的团数至多为2。

相关定理

• 图兰定理给出了稠密图中团的大小的下界。^[2]如果一张图有足够多条边，那么它肯定包含一个大团。例如，对于任意${\displaystyle n}$阶图，如果它的边数大于${\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil }$，那么它必然包含一个${\displaystyle 3}$阶团。
• 拉姆齐定理指出，任意图或者它的补图包含这样的团，它具有至少为对数大小的点数。^[3]
• Moon & Moser 指出，阶数为${\displaystyle 3n}$的图至多有${\displaystyle 3^{n}}$个极大团。极大值在 Moon-Moser 图${\displaystyle K_{3,3,\dots }}$取得，这是图兰图（英语：Turán_graph）的在图兰定理下的一种极端情况。^[4]
• Hadwiger猜想（英语：Hadwiger_conjecture_(graph_theory)）给出了最大团大小与色数之间的关系。
• Erdős–Faber–Lovász猜想（英语：Erdős–Faber–Lovász_conjecture）给出了图着色与团之间的关系。

分团问题

主条目：分团问题

在计算复杂性理论中，分团问题（clique problem）在给定图中寻找最大团的问题。它是图论中的一个NP完全问题。人们在分团问题上提出了许多算法，指数时间复杂度算法包括Bron–Kerbosch算法（英语：Bron–Kerbosch_algorithm），而针对特定一类图有多项式时间复杂度算法，例如平面图和完美图（英语：Perfect_graph）。

注释

1. 其实Kuratowski (1930) harvtxt模板错误: 无指向目标: CITEREFKuratowski1930 (帮助)更早提出完全子图一词（一个有限图是平面图，当且仅当它不包含完全子图或完全二分子图），但作者在最初的措辞着意于拓扑术语，而非图论术语.
2. Turán, Paul, On an extremal problem in graph theory, Matematikai és Fizikai Lapok, 1941, 48: 436–452 （匈牙利语）
3. Graham, R.; Rothschild, B.; Spencer, J. H., Ramsey Theory, New York: John Wiley and Sons, 1990, ISBN 978-0-471-50046-9 含有内容需登入查看的页面 (link)
4. Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 1965, 3: 23–28, MR 0182577, doi:10.1007/BF02760024

参考文献

• Erdős, Paul; Szekeres, George, A combinatorial problem in geometry (PDF), Compositio Math., 1935, 2: 463–470 [2013-08-22], （原始内容存档 (PDF)于2020-05-22）.

• [R. Duncan]; Perry, Albert D., A method of matrix analysis of group structure, Psychometrika, 1949, 14 (2): 95–116, PMID 18152948, doi:10.1007/BF02289146 请检查|author-link1=值 (帮助).

外部链接

• 埃里克·韦斯坦因. Clique. MathWorld.
• 埃里克·韦斯坦因. Clique Number. MathWorld.