团 (图论)

✍ dations ◷ 2025-11-30 20:57:14 #图论

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

相关

  • 超能力超能力(英语:Super-powers;德语:Psi-Phänomen,Psi来自希腊词ψυχή〔Psyche〕,义为“心灵”、“灵魂”、“精神”,即英文“精神病”psycho的词源),又称为特异功能,是指心灵感应、透
  • 布拉维晶格布拉维晶格(又译布拉维点阵)(Bravais lattices) 在几何学以及晶体学中,只有14种可能。常见的布拉维晶格列于下表:每一个单位晶格的体积可以由
  • 托马斯·凯利托马斯·J·凯利(英语:Thomas J. Kelly1941年11月21日-),美国癌症研究人员,其工作重点是DNA复制的分子机制。凯利是纪念斯隆 - 凯特琳癌症中心的主任,并且是该中心纪念Benno C. Sc
  • 隼鸟号可见光谱成相仪(AMICA) 远距光学导航相机(ONC-T) 广角光学导航相机(ONC-W) 光学雷达(LIDAR) 近红外线光谱仪(NIRS) X射线光谱仪(XRS) 目标标定球(Target Marker, TM)隼鸟号(日文:はやぶさ,开
  • 密码在密码学中,加密(英语:Encryption)是将明文信息改变为难以读取的密文内容,使之不可读的过程。只有拥有解密方法的对象,经由解密过程,才能将密文还原为正常可读的内容。虽然加密作为
  • 多米尼克总统多米尼克总统是多米尼克1978年从英国独立后的国家元首,但日常权力由总理行使。阿根廷总统 · 巴拉圭总统 · 巴拿马总统 · 巴西总统(沿革:君主) · 加拿大君主(总督) · 秘鲁总
  • 湘桂.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none
  • 磷杂乙炔磷杂乙炔是一种无色气体,化学式HCP,结构式H—C≡P。磷杂乙炔可以由磷化氢通过炭电弧放电得到,同时也产生乙炔和乙烷,或者由H3CPCl2热分解得到,副产物氯化氢。磷杂乙炔不稳定,仅在
  • 牡丹皮牡丹皮,简称“丹皮”,是一种中草药,即牡丹的根皮。牡丹皮味道苦辛,中医理论认为其性微寒,具有凉血、清热、散瘀的功能。中医上用来主治血热发斑、吐血、鼻衄、劳热骨蒸、经闭症瘕
  • 欧盟关税同盟本文是 欧洲联盟的政治与政府 系列条目之一欧盟关税同盟(英语:European Union Customs Union (EUCU),法语:Union douanière de l'Union européenne,德语:Europäische Zollunion