团 (图论)

✍ dations ◷ 2025-07-26 15:57:58 #图论

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

虽然对完全子图的研究可以追溯到Erdős & Szekeres(1935)中拉姆齐理论对图理论的重组,“团”这一术语本身其实源自 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的补图中的独立集是一一对应的。

相关

  • 结构域蛋白质结构域(英语:protein domain)是蛋白质中的一类结构单元,是构成蛋白质(三级)结构的基本单元。有些球形蛋白的一条肽链,或以共价键相连的两条或多条肽链在空间结构上可以区分为
  • 乔治·福克斯乔治·福克斯(George Fox,1624年7月-1691年1月13日)是一位英国重要的反对国教派人士。普遍认为他是贵格会(或公谊会)的创始人。他生活在一个社会剧变的时代,为了他不寻常和不妥协的
  • 捷运站地铁站,台湾称作捷运站,为属于城市轨道交通系统的铁路车站,通常采用地下或高架方式建构车站。多线交会的地铁站可能有许多层,一般分为大堂和月台,因此必须装设大量电扶梯、楼梯及
  • 无花果属榕属(学名:Ficus),又名无花果属,是桑科内的其中一属也是无花果族(学名:Ficeae)的唯一属,内里包含近八百种的树木、灌木及藤本植物等。它们原为热带雨林的原生品种,但也有部分延伸至暖
  • 欧亚局中国人民解放军军徽中央军委国际军事合作办公室欧亚局,位于北京市,是中央军委国际军事合作办公室下属局,负责该办公室欧亚业务。原先国防部外事办公室设有国防部外事办公室欧亚
  • 菲律宾海沟菲律宾海沟是位于菲律宾群岛以东的海沟,从吕宋岛之东北方伸延至印尼哈马黑拉的摩鹿加群岛,长约1,320公里,阔约30公里。其最深处深约10,540米。菲律宾海沟形成的原因是板块的碰
  • 蒙古高压西伯利亚高压或蒙古高压,是一典型的半永久性大陆反气旋中心。由于海陆热力性质差异的缘故,在蒙古、西伯利亚一带形成大范围的冷高压,也因此,在冬季时大陆降温较快,海洋降温则较慢
  • 安妮·奥克利安妮·奥克利(Annie Oakley,1860年8月13日-1926年11月3日)是十九世纪闻名美国西部的女神枪手。她的惊人天赋在15岁时首次曝光,在枪击比赛中击败另一名神枪手法兰克·E·巴特勒,之
  • 香叶月桂(学名:),又称月桂树、桂冠树、甜月桂、月桂冠,是调味料月桂叶的来源。原产于地中海沿岸及小亚细亚一带灌木岩石区,现已遍布世界各地。叶片深绿色,椭圆形,革质,味苦,清香。干燥后,苦
  • 酮酸中毒酮酸中毒(英语:Ketoacidosis),是一种病理性代谢状态,标志为极高且无法控制的酮症。酮酸中毒的情况下,人体无法足够地控制酮类的产生,导致严重的酮酸堆积使得血液pH极大地降低。在极