查看“︁團 (圖論)”︁的源代码

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

虽然对[[完全图|完全子图]]的研究可以追溯到{{harvtxt|Erdős|Szekeres|1935}}中[[拉姆齐理论]]对图理论的重组<ref>其实{{harvtxt|Kuratowski|1930}}更早提出[[完全图|完全子图]]一词（一个有限图是[[平面图_(图论)|平面图]]，当且仅当它不包含[[完全图|完全子图]]或[[完全二分图|完全二分子图]]），但作者在最初的措辞着意于拓扑术语，而非图论术语.</ref>，“团”这一术语本身其实源自 {{harvtxt|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的'''{{link-en|二分维数|Bipartite dimension}}'''是指覆盖G中所有边所需要的最少的二分团的数目，其中'''二分团'''（biclique）就是[[完全二分图|完全二分子图]] 。而[[分团覆盖问题]] （Clique cover problem）所关心的是用最少的团去覆盖G中所有的[[顶点 (图论)|顶点]]。

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

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

==相关定理==
* [[图兰定理]]给出了稠密图中团的大小的下界。<ref>{{citation|last = Turán| first = Paul | author-link = 圖蘭·帕爾| year = 1941| title = On an extremal problem in graph theory| journal = Matematikai és Fizikai Lapok| volume = 48| pages = 436–452| language = hu}}</ref>如果一张图有足够多条边，那么它肯定包含一个大团。例如，对于任意<math>n</math>阶图，如果它的边数大于<math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math>，那么它必然包含一个<math>3</math>阶团。
* [[拉姆齐定理]]指出，任意图或者它的[[補圖|补图]]包含这样的团，它具有至少为对数大小的点数。<ref>{{citation| last1 = Graham| first1 = R.| author1-link = Ronald Graham| last2 = Rothschild| first2 = B.| last3 = Spencer| first3 = J. H.| author3-link = Joel Spencer| location = New York| publisher = John Wiley and Sons| title = Ramsey Theory| year = 1990| isbn = 978-0-471-50046-9| url-access = registration| url = https://archive.org/details/ramseytheory0000grah}}</ref>
* Moon & Moser 指出，阶数为<math>3n</math>的图至多有<math>3^n</math>个极大团。极大值在 Moon-Moser 图<math>K_{3,3,\dots}</math>取得，这是{{tsl|en|Turán_graph|图兰图}}的在图兰定理下的一种极端情况。<ref>{{citation| last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L.| title = On cliques in graphs| journal = Israel J. Math.| volume = 3| year = 1965| pages = 23–28| mr = 0182577 | doi = 10.1007/BF02760024}}</ref>
* {{tsl|en|Hadwiger_conjecture_(graph_theory)|Hadwiger猜想}}给出了最大团大小与[[图着色问题|色数]]之间的关系。
* {{tsl|en|Erdős–Faber–Lovász_conjecture|Erdős–Faber–Lovász猜想}}给出了图着色与团之间的关系。

==分团问题==
{{main|分團問題}}
在[[计算复杂性理论]]中，分团问题（clique problem）在给定图中寻找最大团的问题。它是[[图论]]中的一个[[NP完全]]问题。人们在分团问题上提出了许多算法，[[EXPTIME|指数时间复杂度]]算法包括{{tsl|en|Bron–Kerbosch_algorithm|Bron–Kerbosch算法}}，而针对特定一类图有[[P_(複雜度)|多项式时间复杂度]]算法，例如[[平面图_(图论)|平面图]]和{{tsl|en|Perfect_graph|完美图}}。

==注释==
{{reflist}}

==参考文献==
{{refbegin|2}}
*{{citation |first1=Paul |last1=Erdős |author1-link=保罗·埃尔德什 |first2=George |last2=Szekeres |author2-link=喬治·塞凱賴什 |title=A combinatorial problem in geometry |journal=Compositio Math. |volume=2 |year=1935 |pages=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf |accessdate=2013-08-22 |archive-date=2020-05-22 |archive-url=https://web.archive.org/web/20200522011619/https://www.renyi.hu/~p_erdos/1935-01.pdf |dead-url=no }}.
{{refend}}
*{{citation
 | last1 = Luce | first1 = R. Duncan | authorlink =http://en.wikipedia.org/wiki/R._Duncan_Luce
 | last2 = Perry | first2 = Albert D.
 | title = A method of matrix analysis of group structure 
 | journal = Psychometrika | volume = 14 | issue = 2 | year = 1949
 | pages = 95–116 | doi = 10.1007/BF02289146
 | pmid = 18152948}}.
==外部链接==
*{{MathWorld|title=Clique|urlname=Clique}}
*{{MathWorld|title=Clique Number|urlname=CliqueNumber}}

{{图论}}

[[Category:图论]]