团 (图论)

✍ dations ◷ 2025-09-18 17:01:49 #图论

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

相关

  • A14ATC代码A(消化系统和代谢系统)是解剖学治疗学及化学分类系统的一个分类,这是由世界卫生组织药物统计方法整合中心(The WHO Collaborating Centre for Drug Statistics Methodolo
  • 仰韶文化、瓮等日用陶器渭河流域河南西部山西河北汉水中上游甘肃洮河流域河套地区仰韶文化是黄河中游地区重要的新石器时代文化,年代约为公元前5000年-公元前3000年前,分布在整个黄河中
  • 范宽范宽(约950年-约1032年),字中立,一说名中正,字仲立,生于五代末,北宋著名画家,京兆华原(今陕西耀县)人。因为性情宽厚豁达,不拘成礼,嗜酒好求道,时人呼之为“宽”,遂以范宽自名。范宽擅长山
  • IERS国际地球自转服务(International Earth Rotation Service,IERS)全称为国际地球自转和参考系服务(International Earth Rotation and Reference Systems Service)。是一家提供全球
  • 猪苓猪苓(Polyporus umbellatus),亦称野猪粪,或称地乌桃、猪茯苓、猪灵芝、猳猪矢、豕槖等。生于长有蜜环菌的阔叶树的根部。地下有多年生菌核,如薯蓣块状,表面棕黑色至灰黑色,子实体生
  • 彼得伯勒彼得伯勒(英语:Peterborough)位于英国英格兰东区域剑桥郡,英格兰的单一管理区、城市。2007年时约有人口161,800人。在这里发现了青铜器时期的遗迹。曾属罗马帝国统治。距离伦敦
  • BBC Radio 2BBC Radio 2是BBC的一个国家级电台,它也是英国最受欢迎的电台之一.Radio2日常播放的音乐以Adult Contemporary或AOR为主。
  • 第三大马远景策划纲要第三大马远景策划纲要(英文:The Third Outline Perspective Plan,简称OPP 3)是马来西亚于2001年至2010年执行的经济政策,为期十年,亦称国家宏愿政策(National Vision Policy)。此政
  • 物理评论快报《物理评论快报》(英语: ,简称PRL),也译作物理报导期刊、物理评论快讯,是一本声誉卓著的物理学期刊,自1958年起开始由美国物理学会出版。该刊是从物理评论延伸出来的刊物。物理评论
  • 吲哚-3-乙酸吲哚-3-乙酸(英语:indole-3-acetic acid),简称吲哚乙酸(英语:indoleacetic acid),又称萮乙酸,缩写为IAA,是一种杂环化合物。它属于一类重要的植物激素——生长素。这种无色的固体很可