团 (图论)

✍ dations ◷ 2025-12-03 07:05:59 #图论

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

相关

  • ProtegeProtégé,常简化拼写为“Protege”,是一个史丹佛大学开发的本体编辑和知识管理系统。开发语言采用Java,属于开放源码软件。由于其优秀的设计和众多的插件,Protégé已成为当前
  • 分子轨道分子轨道(英语:Molecular orbital, MO)是化学中用以描述分子中电子的波动特性的函数。这个函数可以计算出化学和物理性质,例如在任意一个特定区域找到电子的概率。“轨道”一词
  • 匙,也称汤匙、匙子、勺、勺子、汤勺、调羹或匙羹,是一种餐具、量具或工具,由带有凹陷的头部和连接的柄构成。用来装液体和小块固体。一般把体积较小、用于进餐的称为“匙”或“
  • 美国海军犯罪调查局Russell-Kno大楼海军犯罪调查局(英语:Naval Criminal Investigative Service),又译海军刑事调查局,是美国海军部隶属下的情报收集机构及反情报、反恐怖主义机构,同时也是美国的一
  • 布雷克·葛里芬布莱克·奥斯汀·格里芬(英语:Blake Austin Griffin,1989年3月16日-),出生于美国俄克拉何马州俄克拉何马城,职业篮球运动员,昵称干篮哥、给力芬、霸王龙。现效力于NBA联盟底特律活塞
  • 吴光长南越(1955-1975)吴光长(越南语:Ngô Quang Trưởng,1929年12月13日-2007年1月22日),是一位越南共和国陆军(南越陆军)的中将。出身于大户人家,高中毕业后参军。于南越军校毕业后,正式
  • 干岩头村干岩头村位于中国湖南省永州市零陵区富家桥镇,又称涧岩头,是中国历史文化名村。有保存较完好的6个明清古建筑院落,其中最大的一座(周家大院)建于清同治年间。坐标:26°01′19″N
  • ATC代码 (C07)A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码C07(β受体阻断药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collab
  • 北准渎北准渎,又称北准渎村,一个自然村落,以欧姓为主,位于太湖西滨,位于洋溪渎南边,属于江苏宜兴市周铁镇。北准渎位于太湖平原,土地肥沃,水网密集,此地居民原来绝大部分务农,从20世纪九十年
  • 乌莉娅娜·谢苗诺娃乌莉娅娜·谢苗诺娃(俄语:Ульяна Семёнова,转写:Uļjana Semjonova,1952年3月9日-)是已退役的苏联-拉脱维亚篮球运动员。身高2.10米,体重120公斤,被誉为“女篮皇后”。