团 (图论)

✍ dations ◷ 2025-11-27 06:36:17 #图论

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

相关

  • 黏着语黏着语(英语:Agglutinative language),为综合语(synthetic language)的一种,具有词形变化的一种语言类型。黏着语透过在名词、动词等词根粘加上不同的词尾来表达语法功能。黏着语与
  • 牛顿定律牛顿运动定律(英语:Newton's laws of motion)描述施加于物体的外力与物体所呈现出的运动彼此之间的关系。这定律被誉为经典力学的基础,是英国物理泰斗艾萨克·牛顿所提出的三条
  • 短效胰岛素短效型胰岛素,又称为中性胰岛素、可溶性胰岛素,作用时间较短。此药物用于治疗第一型糖尿病、第二型糖尿病、妊娠性糖尿病以及各种糖尿病所引发的并发症,包括糖尿病酮酸血症、高
  • 麦克马斯特大学坐标:43°15′34″N 79°55′8″W / 43.25944°N 79.91889°W / 43.25944; -79.91889麦克马斯特大学(英语:McMaster University)是加拿大安大略省哈密尔顿的一间研究型公立大学,
  • 莫比乌斯 最终幻想《莫比乌斯 最终幻想》(日语:メビウスフ ァイナルファンタジー,Mobius Final Fantasy)是一部由史克威尔艾尼克斯制作并发行在智能手机iOS和Android平台以及Windows平台上的《最
  • 洛克希德马丁洛克希德·马丁(英语:Lockheed Martin,NYSE:LMT)是一家美国航空航天制造厂商,1995年由洛克希德公司与马丁·玛丽埃塔公司共同合并而成。 洛克希德·马丁以开发、制造军用飞机闻名
  • 本体论证明本体论证明(Ontological argument)是证明上帝存在的一种理论,属于先验性的证明方式。该理论最早由中世纪哲学家伊本·西那和安瑟伦提出。后世的哲学家,包括谢哈布丁·苏哈拉瓦迪
  • 环太平洋火山带环太平洋火山带(英语:Ring of Fire,又称环太平洋带、环太平洋地震带或火环带)是一个围绕太平洋经常发生地震和火山爆发的地区,全长40,000千米,呈马蹄形。环太平洋火山带上有一连串
  • 三菱日联银行三菱日联银行(日语:三菱UFJ銀行/みつびしユーエフジェイぎんこう  */?,英语译名:MUFG Bank)是日本一家都市银行,由东京三菱银行与UFJ银行在2006年1月1日合并而成,隶属日本资产最庞
  • 血汗症血汗症(Hematidrosis)也称为血汗(blood sweat)是流汗时汗液中会带有血液的罕见疾病。血汗症的原文源自古希腊语 (αἷμα/αἵματος,意思是血)及(ἱδρώς,意思是汗)。血汗一