团 (图论)

✍ dations ◷ 2025-12-07 15:51:57 #图论

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

相关

  • 医学院医学院是高等教育体制下的一个学院,课程安排主要是以培养和医学相关专门人才和研究人员为目的。医学院的科系和研究所,大致可分为临床医学和基础医学。临床医学部分包括了医学
  • 数位数码(英语:digital)通常指一个数码系统,它使用离散(即不连续的)值(0或1)代表信息,用以输入,处理,传输、贮存等。相对的非数码(模拟信号)系统使用一个个连续的范围代表信息。虽然数码的表
  • 科西嘉语法国科西嘉科西嘉语是罗曼语族的一个分支,为法国本土东南方科西嘉岛居民使用,并被定为当地的官方语言。在意大利撒丁岛的加卢拉和萨萨里也有它的外延。科西嘉语与意大利语相近
  • 联邦共和国联邦共和国(federal republic)是指实施联邦制的共和制国家。共和制是指拥有民选国家领导人,而非君主的国家。在联邦共和国,联邦政府和各个地方政府之间有权力分工。虽然不同国家
  • RIP路由信息协议(英语:Routing Information Protocol,缩写:RIP)是一种内部网关协议(IGP),为最早出现的距离向量路由协议。属于网络层,其主要应用于规模较小的、可靠性要求较低的网络,可以
  • 新古典学派犯罪学(英语:Criminology)是一门社会科学,主题是寻找犯罪行为的现象与规律,寻找犯罪发生的原因,借此寻找方法以减轻犯罪对社会的影响(最后这项于今日已被更精致地分科为刑事政策,而
  • 江户城江户城(日语:江戸城/えどじょう edo jō */?)是位于日本东京都千代田区千代田(古武藏国丰岛郡江户)的城堡,别名为江城(江城/こうじょう kōjō ?)、千代田城(千代田城/ちよだじょう
  • 湘南土话湘南土话也称为平话,主要分布在湖南省南部的郴州和永州地区,内部差异较大。湘南土话不同于流行于湖南省大部分地区的湘语,与郴州市城区流行的郴州官话更是截然不同。湘南土话是
  • 吸血蝠亚科吸血蝠亚科(英文:Vampire bat)是属于脊索动物门哺乳纲翼手目叶口蝠科的亚科,含有吸血蝠、毛腿吸血蝠和白翼吸血蝠三个种,都原产于美洲。亚科名“Desmodontinae”出自古希腊文词“
  • 希腊饮食希腊饮食(希腊语:Ελληνική Κουζίνα)为典型的地中海风格,受意大利、巴尔干诸国、土耳其等国影响。广泛使用橄榄油、蔬菜、香草、谷物,以及面包、酒、鱼,各种肉类,包