团 (图论)

✍ dations ◷ 2025-11-17 12:39:40 #图论

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

相关

  • 先天性无齿症在牙医学上,先天性无齿症是一种罕见的遗传性疾病,患者缺少的可能是乳齿或恒齿。此症与外胚层发育不良有关,因此时常伴随着皮肤及神经方面的相关疾病发生。先天性无齿症虽然包含
  • 可数名词可数名词(Countable noun)是名词的分类之一,与不可数名词(Uncountable noun)相对。也可理解为可知准数量词。在英语等欧洲语言中,可数名词通常会出现众数形式。汉语语法中并无严
  • 巴塔萨·纽曼约翰·巴尔塔萨·诺伊曼(德语:Johann Balthasar Neumann,1687年1月30日-1753年8月19日),通常称为巴尔塔萨·诺伊曼(Balthasar Neumann),为德国建筑师,是巴洛克建筑的重要代表人物。推
  • 刑部刑部是中国古代官署名之一。其长官为刑部尚书。刑部最早出自隋朝五省六曹制,其时设有都官尚书,后来改为刑部尚书,为六部之一,长官为刑部尚书。其后由唐至元,此制历代相沿。唐玄宗
  • 认知过程认知或认识(英语:cognition)在心理学中是指通过形成概念、知觉、判断或想象等心理活动来获取知识的过程,即个体思维进行信息处理的心理功能。认知过程可以是自然的或人造的、有
  • 狒狒阿拉伯狒狒 Papio hamadryas 几内亚狒狒 Papio papio 东非狒狒 Papio anubis 草原狒狒 Papio cynocephalus 豚尾狒狒 Papio ursinus狒狒属,猴科的一属,是世界上体型仅次于山魈
  • 杜丽杜丽(1982年3月5日-),中国女子射击运动员,山东淄博沂源人,2004年雅典奥运会首金获得者和2008年北京奥运会50米运动步枪三姿冠军。其丈夫是奥运冠军庞伟。2016年8月12日,宣布退役,不
  • 复数 (语法)复数,或称众数(英语:plural,可简写为pl),在语言学中是词素的其中一种,常和单数相对,在没有双数概念的语言中用于标示多于一个的物件,在有双数概念的语言中则表示多于两个的名词数量。
  • 艾瑞克·威斯乔斯艾瑞克·威斯乔斯,(Eric F. Wieschaus,1947年6月8日-),美国发育生物学家,1995年获得诺贝尔生理学或医学奖。出生于印第安纳南本德,圣母大学本科毕业,耶鲁大学博士。1978年开始在欧洲
  • 地平说学会地平说学会(英语:Flat Earth Society)又称国际地平说学会(英语:International Flat Earth Society)或者国际地平说考证学会(英语:International Flat Earth Research Society),是一个