定义 顶点集C被称为无向图 G=(V,E) 的团 ，如果C是顶点 集V的子集(C⊆V)，而且任意两个C中的顶点都有边 连接。另一种等价的说法是，由C诱导的子图是完全图 （有时也用“团”来指这样的子图）。
极大团 是指增加任一顶点都不再符合团定义的团，也就是说，极大团不能被任何一个更大的团所包含。
最大团 是一个图中顶点数最多的团。图G的团数 （clique number）ω(G) 是指G中最大团的顶点数。图G的边团覆盖数 （edge clique cover number）是指覆盖G中所有的边所需要的最少的团的数目。图G的二分维数 二分团 （biclique）就是完全二分子图 。而分团覆盖问题 （Clique cover problem）所关心的是用最少的团去覆盖G中所有的顶点 。
独立集 补图 中的独立集是一一对应的。
相关性质 Cluster graph 连通分量 为团。Block graph 2-连通分量 弦图 的点具有完美消去序（perfect elimination ordering），这种排序具有如下性质：对于所有的点 v {\displaystyle v} N ( v ) {\displaystyle N(v)} v {\displaystyle v} v {\displaystyle v} Cograph 极大独立集 Interval graph v {\displaystyle v} v {\displaystyle v} 线图 的边能被一些没有公共边的团所覆盖，并且每个点恰好属于两个团。完美图 导出子图 的团数等于色数 。Split graph Triangle-free graph
相关定理 图兰定理 给出了稠密图中团的大小的下界。[2] n {\displaystyle n} ⌊ n 2 ⌋ ⋅ ⌈ n 2 ⌉ {\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil } 3 {\displaystyle 3} 拉姆齐定理 指出，任意图或者它的补图 包含这样的团，它具有至少为对数大小的点数。[3] Moon & Moser 指出，阶数为 3 n {\displaystyle 3n} 3 n {\displaystyle 3^{n}} K 3 , 3 , … {\displaystyle K_{3,3,\dots }} 图兰图 [4] Hadwiger猜想 色数 之间的关系。Erdős–Faber–Lovász猜想
分团问题
注释 ^ 其实Kuratowski (1930 )更早提出完全子图 一词（一个有限图是平面图 ，当且仅当它不包含完全子图 或完全二分子图 ），但作者在最初的措辞着意于拓扑术语，而非图论术语. ^ Turán, Paul , On an extremal problem in graph theory, Matematikai és Fizikai Lapok, 1941, 48 : 436–452 （匈牙利语） ^ Graham, R.; Rothschild, B.; Spencer, J. H., Ramsey Theory , New York: John Wiley and Sons, 1990, ISBN 978-0-471-50046-9 ^ Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 1965, 3 : 23–28, MR 0182577 , doi:10.1007/BF02760024
参考文献 Erdős, Paul ; Szekeres, George , A combinatorial problem in geometry (PDF) , Compositio Math., 1935, 2 : 463–470 [2013-08-22 ] , （原始内容 (PDF) 于2020-05-22） [R. Duncan]; Perry, Albert D., A method of matrix analysis of group structure, Psychometrika, 1949, 14 (2): 95–116, PMID 18152948 , doi:10.1007/BF02289146
外部链接
圖論, 在图论领域的一个无向图中, 满足两两之间有边连接的顶点的集合, 被称为该无向图的团, 团是图论中的基本概念之一, 用在很多数学问题以及图的构造上, 计算机科学中也有对它的研究, 尽管在一个图中寻找给定大小的团达到了np完全的难度, 人们还是研究过很多寻找团的算法, 虽然对完全子图的研究可以追溯到erdős, szekeres, 1935, 中拉姆齐理论对图理论的重组, 这一术语本身其实源自, luce, perry, 1949, 那篇文章中社会网络的完全子图被用来模拟一, 也就是一组两两相互认识的人, 团在. 在图论领域的一个无向图中 满足两两之间有边连接的顶点的集合 被称为该无向图的团 团是图论中的基本概念之一 用在很多数学问题以及图的构造上 计算机科学中也有对它的研究 尽管在一个图中寻找给定大小的团达到了NP完全的难度 人们还是研究过很多寻找团的算法 虽然对完全子图的研究可以追溯到Erdos amp Szekeres 1935 中拉姆齐理论对图理论的重组 1 团 这一术语本身其实源自 Luce amp Perry 1949 那篇文章中社会网络的完全子图被用来模拟一 团 人 也就是一组两两相互认识的人 团在科学领域特别是在生物信息学中有许多其他应用 目录 1 定义 2 相关性质 3 相关定理 4 分团问题 5 注释 6 参考文献 7 外部链接定义 编辑顶点集C被称为无向图 G V E 的团 如果C是顶点集V的子集 C V 而且任意两个C中的顶点都有边连接 另一种等价的说法是 由C诱导的子图是完全图 有时也用 团 来指这样的子图 极大团是指增加任一顶点都不再符合团定义的团 也就是说 极大团不能被任何一个更大的团所包含 最大团是一个图中顶点数最多的团 图G的团数 clique number w G 是指G中最大团的顶点数 图G的边团覆盖数 edge clique cover number 是指覆盖G中所有的边所需要的最少的团的数目 图G的二分维数 英语 Bipartite dimension 是指覆盖G中所有边所需要的最少的二分团的数目 其中二分团 biclique 就是完全二分子图 而分团覆盖问题 Clique cover problem 所关心的是用最少的团去覆盖G中所有的顶点 独立集是刚好和团相反的概念 因为图G中的团和图G的补图中的独立集是一一对应的 相关性质 编辑Cluster graph 英语 Cluster graph 的连通分量为团 Block graph 英语 Block graph 的2 连通分量 英语 Biconnected component 为团 弦图的点具有完美消去序 perfect elimination ordering 这种排序具有如下性质 对于所有的点v displaystyle v N v displaystyle N v 中排序在v displaystyle v 后的点和v displaystyle v 共同构成一个团 Cograph 英语 Cograph 的所有导出子图具有如下性质 任意极大团与任意极大独立集 英语 Maximal independent set 有且仅有一个共同点 Interval graph 英语 Interval graph 的极大团可以按照如下方式排序 对于任意点v displaystyle v 包含v displaystyle v 的团在排序中是连续的 线图的边能被一些没有公共边的团所覆盖 并且每个点恰好属于两个团 完美图 英语 Perfect graph 的所有导出子图的团数等于色数 Split graph 英语 Split graph 包含具有如下性质的团 对于图中每条边 至少包含一个顶点 Triangle free graph 英语 Triangle free graph 的团数至多为2 相关定理 编辑图兰定理给出了稠密图中团的大小的下界 2 如果一张图有足够多条边 那么它肯定包含一个大团 例如 对于任意n displaystyle n 阶图 如果它的边数大于 n 2 n 2 displaystyle scriptstyle lfloor frac n 2 rfloor cdot lceil frac n 2 rceil 那么它必然包含一个3 displaystyle 3 阶团 拉姆齐定理指出 任意图或者它的补图包含这样的团 它具有至少为对数大小的点数 3 Moon amp Moser 指出 阶数为3 n displaystyle 3n 的图至多有3 n displaystyle 3 n 个极大团 极大值在 Moon Moser 图K 3 3 displaystyle K 3 3 dots 取得 这是图兰图 英语 Turan graph 的在图兰定理下的一种极端情况 4 Hadwiger猜想 英语 Hadwiger conjecture graph theory 给出了最大团大小与色数之间的关系 Erdos Faber Lovasz猜想 英语 Erdos Faber Lovasz conjecture 给出了图着色与团之间的关系 分团问题 编辑主条目 分團問題 在计算复杂性理论中 分团问题 clique problem 在给定图中寻找最大团的问题 它是图论中的一个NP完全问题 人们在分团问题上提出了许多算法 指数时间复杂度算法包括Bron Kerbosch算法 英语 Bron Kerbosch algorithm 而针对特定一类图有多项式时间复杂度算法 例如平面图和完美图 英语 Perfect graph 注释 编辑 其实Kuratowski 1930 更早提出完全子图一词 一个有限图是平面图 当且仅当它不包含完全子图或完全二分子图 但作者在最初的措辞着意于拓扑术语 而非图论术语 Turan Paul On an extremal problem in graph theory Matematikai es Fizikai Lapok 1941 48 436 452 匈牙利语 Graham R Rothschild B Spencer J H Ramsey Theory New York John Wiley and Sons 1990 ISBN 978 0 471 50046 9 含有內容需登入查看的頁面 link Moon J W Moser L On cliques in graphs Israel J Math 1965 3 23 28 MR 0182577 doi 10 1007 BF02760024 参考文献 编辑Erdos Paul Szekeres George A combinatorial problem in geometry PDF Compositio Math 1935 2 463 470 2013 08 22 原始内容存档 PDF 于2020 05 22 R Duncan Perry Albert D A method of matrix analysis of group structure Psychometrika 1949 14 2 95 116 PMID 18152948 doi 10 1007 BF02289146 请检查 author link1 值 帮助 外部链接 编辑埃里克 韦斯坦因 Clique MathWorld 埃里克 韦斯坦因 Clique Number MathWorld 取自 https zh wikipedia org w index php title 團 圖論 amp oldid 66611577, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。