图论领域的一个无向图中,满足两两之间有连接的顶点集合,被称为该无向图的团。团是图论中的基本概念之一,用在很多数学问题以及图的构造上。计算机科学中也有对它的研究,尽管在一个图中寻找给定大小的团达到了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_graph2-连通分量英语Biconnected_component为团。
  • 弦图的点具有完美消去序(perfect elimination ordering),这种排序具有如下性质:对于所有的点中排序在后的点和共同构成一个团。
  • Cograph英语Cograph的所有导出子图具有如下性质:任意极大团与任意极大独立集英语Maximal_independent_set有且仅有一个共同点。
  • Interval graph英语Interval_graph的极大团可以按照如下方式排序:对于任意点包含的团在排序中是连续的。
  • 线图的边能被一些没有公共边的团所覆盖,并且每个点恰好属于两个团。
  • 完美图英语Perfect_graph的所有导出子图的团数等于色数
  • Split graph英语Split_graph包含具有如下性质的团:对于图中每条边,至少包含一个顶点。
  • Triangle-free graph英语Triangle-free_graph的团数至多为2。

相关定理

  • 图兰定理给出了稠密图中团的大小的下界。[2]如果一张图有足够多条边,那么它肯定包含一个大团。例如,对于任意阶图,如果它的边数大于,那么它必然包含一个阶团。
  • 拉姆齐定理指出,任意图或者它的补图包含这样的团,它具有至少为对数大小的点数。[3]
  • Moon & Moser 指出,阶数为的图至多有个极大团。极大值在 Moon-Moser 图取得,这是图兰图英语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

注释

参考文献

外部链接

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.