团 (图论)

✍ dations ◷ 2025-07-03 12:44:16 #图论

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

相关

  • 批判社区心理学批判社区心理学 (英文:Critical Community Psychology)是一个新的领域,主要为“批判心理学”(Critical Psychology)与“社区心理学”(Community Psychology)的结合体。换言之,
  • 国家与政治实体索引 国防预算 石油储量 军事(武装部队) 死刑 国债 生育率 最高点 官方语言 地理 政体 面积 代码 陆地面积 人口 人口密度 国内生产总值 国徽 国旗 国歌 国家格言 首都 城市
  • 鲍鱼鲍属(学名:Haliotis),古称鳆、鳆鱼、海耳,又名镜面鱼、九孔螺、明目鱼,是鲍科(Haliotidae)唯一的一个属。它是一类海洋腹足纲软体动物(也就是一种海螺),栖石质河岸,以藻类为食。鲍鱼是中
  • 胡利奥·科塔萨尔胡利奥·科塔萨尔(西班牙语:Julio Cortázar,原名Jules Florencio Cortázar,1914年8月26日-1984年2月12日),阿根廷作家、学者,拉丁美洲文学爆炸的代表人物之一。1914年8月26日胡利
  • 下加利福尼亚州^ a. 2010 and later, Baja California is the only state to use the USA DST schedule state wide, while the rest of Mexico (except for small portions of other nor
  • 辉南辉南县是吉林省通化市下辖的一个县。前身是晚清时设置的辉南直隶厅。下辖14个镇、3个乡、1个民族乡:朝阳镇、辉南镇、样子哨镇、杉松岗镇、石道河镇、辉发城镇、抚民镇、金川
  • 宣和宣和(1119年二月-1125年)是宋徽宗的第六个年号和最后一个年号。北宋使用宣和这个年号一共7年,由于当时改元仓促,就用宣和殿中的“宣和”两字作为年号。宣和七年二月宋钦宗即位沿
  • 洛克希德L-1011洛克希德三星(Lockheed L-1011 TriStar)是一款中长程,宽体三发动机喷气机。它是继波音747和DC-10后,第三款投入商业运营的宽体喷气客机,亦是洛克希德公司的唯一一款喷气民航客机
  • 咬合咬合,又称�(Occlusion),是牙科术语,即是牙齿对应;通常是指上颌骨与下颌骨的牙齿对应,当咀嚼或休息时两者的接触时间。�字由四川大学华西口腔医学院第二任院长邹海帆在1920年代、1930
  • 2015年东南亚运动会马来西亚代表团马来西亚代表团已参加2015年6月5日至6月15日的新加坡第二十八届东南亚运动会。