團 (圖論)

维基百科,自由的百科全书
跳转至: 导航搜索

图论领域的一个无向图中,满足两两之间有连接的顶点集合,被称为该无向图的团。团是图论中的基本概念之一,用在很多数学问题以及图的构造上。计算机科学中也有对它的研究,尽管在一个图中寻找给定大小的团达到了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中所有的顶点

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

注释[编辑]

  1. ^ 其实Kuratowski (1930)更早提出完全子图一词(一个有限图是平面图,当且仅当它不包含完全子图完全二分子图),但作者在最初的措辞着意于拓扑术语,而非图论术语.

参考文献[编辑]

外部链接[编辑]