团 (图论)

✍ dations ◷ 2025-12-11 15:27:39 #图论

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

相关

  • 秘教秘教,又称秘仪、密仪、密教、密意主义、密传教义等,指在一小众人间相传的秘密知识,及其组织和传授方式,被广泛认为是一个宗教术语,通常涉及神秘性、精神性或隐匿性的观点。秘教的
  • 光线光通常指的是人类眼睛可以见的电磁波(可见光),视知觉就是对于可见光的知觉。可见光只是电磁波谱上的某一段频谱,一般是定义为波长介于400至700奈(纳)米(nm)之间的电磁波,也就是波长比
  • 钻石纳米晶体聚合钻石纳米棒(英语:Aggregated diamond nanorods,又称钻石纳米棒聚合体,简称ADNR),是一种纳米级晶型钻石,又称纳米钻石(nanodiamond)或超钻石(hyperdiamond)。聚合钻石纳米棒是于2003
  • 德克萨斯理工大学德克萨斯理工大学 (英文Texas Tech University,缩写为TTU,也常译为德州理工大学),是一所位于美国德克萨斯州拉伯克市的研究型大学,学校成立于1923年2月10号,最初称为德克萨斯技术学
  • 1975年 利维尼奥第八届冬季世界大学生运动会于1975年4月6日至13日在意大利利维尼奥举行。这是意大利第二次主办冬季世界大学生运动会。该届比赛仅设两个大项。*  主办国家/地区(意大利)
  • 木犀属木樨属(学名:Osmanthus),或称木犀属、桂花属、桂花树属,木樨科常绿灌木或小乔木,原产于亚洲温带。叶对生,呈椭圆或长椭圆形,光滑,革质,有的品种叶边有锯齿。花簇生,一般为白色,有香味。
  • 美国小儿科学会美国儿科学会(英语:American Academy of Pediatrics,簡稱AAP)是美国的儿科研究学会,总部位于伊利诺伊州埃尔克格罗夫村(英语:Elk Grove Village),并在华盛顿特区设有办公室。该学会由
  • 热胀冷缩热胀冷缩是指物体受热时会膨胀,遇冷时会收缩的特性。由于物体内的粒子(原子)运动会随温度改变,当温度上升时,粒子的振动幅度加大,令物体膨胀;但当温度下降时,粒子的振动幅度便会减少
  • 包头市第一中学包头市第一中学地处内蒙古包头市东河区环城路,是自治区首批重点中学,始建于1925年6月12日,前身为绥远二中,由当时西北边防督办冯玉祥将军创办,首任校长为孙则让,是自治区建校最早
  • 专家组报告专家组报告(Panel Report)是世界贸易组织争端解决机制裁决的一个环节。通常而言,在世界贸易组织成员之间发生贸易纠纷时,世界贸易组织将设立独立的专家组(Panel)来审理争端。专家