团 (图论)

✍ dations ◷ 2025-05-20 11:24:15 #图论

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

相关

  • 运动损伤运动损伤又称运动创伤或运动伤害(英语:Sports injuries),指在体育运动或体能锻炼过程中发生的创伤。例如在美国,据估计有三千万青少年参与过某种形式的有组织运动,其中每年又有三
  • 童增童增(1956年-)祖籍湖北黄陂,生于重庆。保钓运动人士。童增生于一个世代书香家庭,祖上有数人参加过辛亥革命,其中三人参加过武昌起义。1982年,童增毕业于四川大学经济系,1986年考入北
  • 光辉城市光辉城市(法语:Ville Radieuse,法语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Ge
  • 卡叠石战役卡迭石战役是古埃及与赫梯王国争夺叙利亚地区统治权而发生的战役。约前1274年5月底埃及第十九王朝的法老拉美西斯二世与赫梯国王在奥伦特河边的卡迭石(叙利亚的大马士革东北)
  • 生态足迹以下有关2007年全世界154个国家生态足迹、生物容量数据由智库Global Footprint Network(英语:Global Footprint Network)提供。
  • 格洛丽亚·阿罗约玛丽亚·格洛丽亚·马卡帕加尔-阿罗约(他加禄语:Maria Gloria Macapagal-Arroyo;1947年4月5日-),是菲律宾第14任总统及第25任众议院议长。不仅是菲律宾第二位女总统,也是前总统奥斯
  • 乌禾尔龙乌禾尔龙(学名:Wellnhoferia grandis)是一属史前鸟类,是始祖鸟的近亲。它生存于侏罗纪晚期的德国。若乌禾尔龙像始祖鸟,它会有一条短尾巴,而第四趾比始祖鸟较短。波兰弗罗茨瓦夫大
  • 亚克兴角战役亚克兴战役(Battle of Actium)是罗马共和国的马克·安东尼与古埃及托勒密王朝法老克利奥帕特拉七世联军与屋大维之间一场决定性战役。此战发生于公元前31年9月2日,地点为希腊阿
  • 索尔·阿林斯基索尔·戴维·阿林斯基(Saul David Alinsky,1909年1月30日-1972年6月12日)美国社区组织家和作家,通常被认为是现代社区组织的创始人。以著作《激进者守则(英语:Rules for Radicals)》
  • 进化论的社会影响现代生物分类群体从它们的 共同祖先遗传分化的图示。进化论介绍(英语:Introduction to evolution) 演化的证据 共同起源 共同起源的证据群体遗传学 · 遗传多样性 突变 ·