团 (图论)

✍ dations ◷ 2025-03-07 11:18:19 #图论

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

相关

  • 淀粉样变类淀粉沉积症(英语:Amyloidosis),又称类淀粉堆积症或淀粉样变,是指类淀粉蛋白(一种异常蛋白质)沉积在组织引起的一类疾病。类淀粉沉积症的病征视乎淀粉样蛋白沉积的所在地而有所不
  • 议会意大利议会(意大利语:Parlamento Italiano)是意大利的最高立法机构。意大利议会为两院制,由参议院、众议院组成。两院职能相同、权力均等。参议院议员315人;众议院议员630人,合共9
  • 步行步行,是指人或其他两足动物使用比跑步慢的速度行。在人类或其他两足动物中,一般来说,步行是用脚步进行的,且在步行阶段中,仅单脚离开地面。相反,在跑步的中开跑的时候,一般均是双脚
  • GeoEye卫星公司GeoEye卫星公司(英语:GeoEye Inc.)是美国一家商用卫星图像公司,坐落于弗吉尼亚州赫恩登,为世界上最大的卫星遥感影像公司,母公司为博龙资产管理。其前身是1992创立的Orbital图像公
  • 明治三陆地震明治三陆地震是一场在日本时间1896年(明治29年)6月15日下午7时32分30秒发生于东北地区三陆外海的地震灾难,是低角逆断层型的海沟型地震。明治三陆地震引发日本史上最具破坏力的
  • 埃施博恩埃施博恩(德语:Eschborn)是德国黑森州的一个市镇。总面积12.13平方公里,总人口20907人,其中男性10183人,女性10724人(2011年12月31日),人口密度1 724人/平方公里。
  • 糖酸糖酸(Sugar acid)是糖类经氧化生成的羧酸。它有以下几种:糖酸(Aldonic acid)很容易由醛糖在温和条件下氧化制备,这个反应常用溴水作氧化剂。酮糖不易被氧化。这个方法可用于分离醛
  • 正辛醇正辛醇 是一种直链脂肪醇,均有8个碳原子,分子式为:CH3(CH2)7OH。主要用于生产增塑剂、萃取剂、稳定剂,用作溶剂和香料的中间体。在增塑剂领域,辛醇一般是指2-乙基己醇,这是百万吨
  • 尼尔·弗格森尼尔·坎贝尔·道格拉斯·弗格森(英语:Niall Ferguson;1964年4月18日-)是位大不列颠国籍的历史学者,现任职为哈佛大学的提胥讲座教授、牛津大学耶稣学院等大学机构的资深研究员。
  • 马格斯·哈弗拉尔马格斯·哈弗拉尔,或荷兰贸易公司的咖啡拍卖(荷兰语:Max Havelaar, of de koffij-veilingen der Nederlandsche Handel-Maatschappij)是穆尔塔图里(Multatuli,是Eduard Douwes Dek