7,129
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条由Jie初步翻译，由Flipped审校。+ + + + 第10行：
第13行： + − In the [[mathematics|mathematical]] area of [[graph theory]], a '''clique''' ({{IPAc-en|ˈ|k|l|iː|k}} or {{IPAc-en|ˈ|k|l|ɪ|k}}) is a subset of vertices of an [[undirected graph]] such that every two distinct vertices in the clique are adjacent; that is, its [[induced subgraph]] is [[complete graph|complete]]. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in [[computer science]]: the task of finding whether there is a clique of a given size in a [[Graph (discrete mathematics)|graph]] (the [[clique problem]]) is [[NP-complete]], but despite this hardness result, many algorithms for finding cliques have been studied. − − In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. − − 在图论的数学领域中，'''<font color="#ff8000"> 团Clique</font>'''是无向图中顶点的子集，使得一个团中每两个不同的顶点必定相邻。也就是说，其导出子图是完全图。团是图论的基本概念之一，可用于图形的构建和解决许多其他数学问题。而且，在计算机科学领域中也经常会涉及到团的研究：比如在一个给定规模的图中寻找团的存在就是一个NP-完全问题。尽管我们已经明确知道这个问题很难得以解决，但仍然有许多学者在研究用于寻找团的算法。 − − − − Although the study of [[complete graph|complete subgraphs]] goes back at least to the graph-theoretic reformulation of [[Ramsey theory]] by {{harvtxt|Erdős|Szekeres|1935}},<ref>The earlier work by {{harvtxt|Kuratowski|1930}} characterizing [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subgraphs was originally phrased in topological rather than graph-theoretic terms.</ref> the term ''clique'' comes from {{harvtxt|Luce|Perry|1949}}, who used complete subgraphs in [[social network]]s to model [[clique]]s of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in [[bioinformatics]]. − − Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term clique comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics. − − 对完全子图的研究至少可以追溯到'''<font color="#ff8000"> 拉姆齐定理Ramsey's theorem</font>'''中的图论重组，由Erdős＆Szekeres（1935）在论文A combinatorial problem in geometry《几何组合问题》提出的。<ref>The earlier work by {{harvtxt|Kuratowski|1930}} characterizing [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subgraphs was originally phrased in topological rather than graph-theoretic terms.</ref>但实际上“团”一词是来自Luce＆Perry（1949）的论文A method of matrix analysis of group structure《群结构矩阵分析的一种方法》，后者在社交网络中使用完全子图来对人群进行建模；该模型定义在这群人中，所有人是互相认识的。其实团这一概念在诸多科学领域中均有所应用，尤其是在生物信息学。 + 第36行：
第28行： + − A '''maximal clique''' is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal. − − A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal. − − '''<font color="#ff8000"> 极大团Maximal clique</font>'''也是一个团，但是不能通过合并更多的相邻节点而进行扩张，换句话说，该团不可能被更大团的顶点集合所包含。有些学者将“极大团”定义为“团”，用其他完全子团的术语来重新定义“非极大团”。 − − − − A '''maximum clique''' of a graph, ''G'', is a clique, such that there is no clique with more vertices. Moreover, the '''clique number''' ω(''G'') of a graph ''G'' is the number of vertices in a maximum clique in ''G''. − − A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices. Moreover, the clique number ω(G) of a graph G is the number of vertices in a maximum clique in G. − − 图''G''中同样存在一个'''<font color="#ff8000"> 最大团Maximum clique</font>'''，使得其不存在更多顶点。另外，图''G''的团数''ω（G）''是该图最大团的顶点数。 − − − − The '''[[intersection number (graph theory)|intersection number]]''' of ''G'' is the smallest number of cliques that together cover all edges of ''G''. − − The intersection number of G is the smallest number of cliques that together cover all edges of G. − − 图''G''的'''<font color="#ff8000"> 交叉数Intersection number</font>'''是该图中同时能覆盖所有连边的最少团数。 − − − − The '''clique cover number''' of a graph ''G'' is the smallest number of cliques of ''G'' whose union covers the set of vertices ''V'' of the graph. − − The clique cover number of a graph G is the smallest number of cliques of G whose union covers the set of vertices V of the graph. − − 图''G''的'''<font color="#ff8000"> 团覆盖数Clique cover number</font>'''指的是能覆盖图''G''中所有顶点集''V''的最少团数。 − − − − A '''maximum clique transversal''' of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.{{sfnp|Chang|Kloks|Lee|2001}} − A maximum clique transversal of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.+ − 一个图的'''<font color="#ff8000"> 最大团横贯集Maximum clique transversal</font>'''是其顶点的子集，其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。 + − The opposite of a clique is an '''[[independent set (graph theory)|independent set]]''', in the sense that every clique corresponds to an independent set in the [[complement graph]]. The [[clique cover]] problem concerns finding as few cliques as possible that include every vertex in the graph.+ − The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph. The clique cover problem concerns finding as few cliques as possible that include every vertex in the graph. − 作为团的对立面，'''<font color="#ff8000"> 独立集Independent set</font>'''是指图中两两互相不相邻的顶点集合。因此，每一个团都对应于补图中的独立集。集团覆盖问题涉及到寻找尽可能少的团，其中包括图中的每个顶点。+ + − A related concept is a '''biclique''', a [[complete bipartite graph|complete bipartite subgraph]]. The [[bipartite dimension]] of a graph is the minimum number of bicliques needed to cover all the edges of the graph. − A related concept is a biclique, a complete bipartite subgraph. The bipartite dimension of a graph is the minimum number of bicliques needed to cover all the edges of the graph.+ − '''<font color="#ff8000"> 二元团biclique</font>'''是团的相关概念，指的是一个完全二分图。该图的二分维度指的是覆盖该图所有连边所需的最少二元团数。 − + − − Mathematical results concerning cliques include the following. − Mathematical results concerning cliques include the following. − + − − *[[Turán's theorem]] gives a [[lower bound]] on the size of a clique in [[dense graph]]s.{{sfnp|Turán|1941}} If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with <math>n</math> vertices and more than <math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math> edges must contain a three-vertex clique. − *[[Ramsey's theorem]] states that every graph or its [[complement graph]] contains a clique with at least a logarithmic number of vertices.{{sfnp|Graham|Rothschild|Spencer|1990}} − *According to a result of {{harvtxt|Moon|Moser|1965}}, a graph with 3''n'' vertices can have at most 3<sup>''n''</sup> maximal cliques. The graphs meeting this bound are the Moon–Moser graphs ''K''<sub>3,3,...</sub>, a special case of the [[Turán graph]]s arising as the extremal cases in Turán's theorem. − *[[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]], still unproven, relates the size of the largest clique [[graph minor|minor]] in a graph (its [[Hadwiger number]]) to its [[chromatic number]]. − *The [[Erdős–Faber–Lovász conjecture]] is another unproven statement relating graph coloring to cliques. − − 第111行：
第58行： − − − Several important classes of graphs may be defined or characterized by their cliques: − Several important classes of graphs may be defined or characterized by their cliques: + + + + + + + + + − *A [[cluster graph]] is a graph whose [[connected component (graph theory)|connected components]] are cliques. − *A [[block graph]] is a graph whose [[biconnected component]]s are cliques. − *A [[chordal graph]] is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the [[neighborhood (graph theory)|neighbors]] of each vertex ''v'' that come later than ''v'' in the ordering form a clique. − *A [[cograph]] is a graph all of whose induced subgraphs have the property that any maximal clique intersects any [[maximal independent set]] in a single vertex. − *An [[interval graph]] is a graph whose maximal cliques can be ordered in such a way that, for each vertex ''v'', the cliques containing ''v'' are consecutive in the ordering. − *A [[line graph]] is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover. − *A [[perfect graph]] is a graph in which the clique number equals the [[chromatic number]] in every [[induced subgraph]]. − *A [[split graph]] is a graph in which some clique contains at least one endpoint of every edge. − *A [[triangle-free graph]] is a graph that has no cliques other than its vertices and edges. − * '''<font color="#ff8000"> 聚类图Cluster graph</font>'''是图的一种特例，其连接的组成部分是团。+ − * '''<font color="#ff8000"> 框图Block graph</font>'''是图的一种特例，其双连通的部分是团。 − * '''<font color="#ff8000"> 弦图Chordal graph</font>'''是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。 − * '''<font color="#ff8000"> 余图Cograph</font>'''是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。 − * '''<font color="#ff8000"> 区间图Interval graph</font>'''是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。 − * '''<font color="#ff8000"> 线图Line graph</font>'''是图的一种特例，其连边可以被边不相交的团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。 − * '''<font color="#ff8000"> 完美图Perfect graph</font>'''是图的一种特例，其导出子图的色数等于此导出子图的团数。 − * '''<font color="#ff8000"> 分裂图Split graph</font>'''是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。 − * '''<font color="#ff8000"> 三角形无关图Triangle-free graph</font>'''是图的一种特例，除了顶点和连边之外，该图不含任何团。 + − Additionally, many other mathematical constructions involve cliques in graphs. Among them,+ − Additionally, many other mathematical constructions involve cliques in graphs. Among them, − 此外，还有许多其他数学结构与图论的"团"有关。它们包括， + + − *The [[clique complex]] of a graph ''G'' is an [[abstract simplicial complex]] ''X''(''G'') with a simplex for every clique in ''G'' − *A [[simplex graph]] is an undirected graph κ(''G'') with a vertex for every clique in a graph ''G'' and an edge connecting two cliques that differ by a single vertex. It is an example of [[median graph]], and is associated with a [[median algebra]] on the cliques of a graph: the median ''m''(''A'',''B'',''C'') of three cliques ''A'', ''B'', and ''C'' is the clique whose vertices belong to at least two of the cliques ''A'', ''B'', and ''C''.<ref>{{harvtxt|Barthélemy|Leclerc|Monjardet|1986}}, page 200.</ref> − *The [[clique-sum]] is a method for combining two graphs by merging them along a shared clique. − *[[Clique-width]] is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques. − *The [[Intersection number (graph theory)|intersection number]] of a graph is the minimum number of cliques needed to cover all the graph's edges. − *The [[clique graph]] of a graph is the [[intersection graph]] of its maximal cliques. − * 图G的'''<font color="#ff8000"> 团复形Clique complex</font>'''属于'''<font color="#ff8000"> 抽象复形Abstract simplicial complex</font>'''，其中图G的每个团都为单纯形。 − * '''<font color="#ff8000"> 单纯形图Simplex graph</font>'''可记为无向图''κ（G）''，它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。它是中线图的一个示例，并且与图中团的中位数相关联：三个团A，B和C的中位团m（A，B，C），其顶点至少属于团A，B和C中的两个。<ref>{{harvtxt|Barthélemy|Leclerc|Monjardet|1986}}, page 200.</ref> − * '''<font color="#ff8000"> 团相加Clique-sum</font>'''指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。 − * '''<font color="#ff8000"> 团宽度Clique-width</font>'''是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。即通过不相交的并集构建图形所需的不同顶点标签的最小数量，通过以下操作建立： − 团宽度为1的图就是团的不相交并集。 − * 图的'''<font color="#ff8000"> 交叉数Intersection number</font>'''指的是能覆盖图所有连边所需的最小团数。 − * 图G的'''<font color="#ff8000"> 团图Clique graph</font>'''指的是该图的极大团的交叉图。主要为了展示图G的团结构。 + − Closely related concepts to complete subgraphs are [[subdivision (graph theory)|subdivision]]s of complete graphs and complete [[graph minor]]s. In particular, [[Kuratowski's theorem]] and [[Wagner's theorem]] characterize [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subdivisions and minors, respectively.+ + − Closely related concepts to complete subgraphs are subdivisions of complete graphs and complete graph minors. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graphs by forbidden complete and complete bipartite subdivisions and minors, respectively. − == Computer science 计算机科学== − − {{main|Clique problem}} − − In [[computer science]], the [[clique problem]] is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is [[NP-complete]], one of [[Karp's 21 NP-complete problems]].{{sfnp|Karp|1972}} It is also [[Parameterized complexity|fixed-parameter intractable]], and [[Hardness of approximation|hard to approximate]]. Nevertheless, many [[algorithm]]s for computing cliques have been developed, either running in [[exponential time]] (such as the [[Bron–Kerbosch algorithm]]) or specialized to graph families such as [[planar graph]]s or [[perfect graph]]s for which the problem can be solved in [[polynomial time]]. − − In computer science, the clique problem is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is NP-complete, one of Karp's 21 NP-complete problems. It is also fixed-parameter intractable, and hard to approximate. Nevertheless, many algorithms for computing cliques have been developed, either running in exponential time (such as the Bron–Kerbosch algorithm) or specialized to graph families such as planar graphs or perfect graphs for which the problem can be solved in polynomial time. − − 在计算机科学中，团问题指的是在给定图中查找最大团或所有团的计算问题。它是是Karp提出的21个NP完全问题之一。它也是固定参数难求解问题，甚至难以获得近似值。尽管如此，目前专业人士已经开发了诸多用于计算团的算法，包括可以在指数时间内求解的例如Bron–Kerbosch算法，以及在多项式时间内专门求解图族（例如平面图或完美图）这类问题的算法。 − − − − == Applications 应用 == − − The word "clique", in its graph-theoretic usage, arose from the work of {{harvtxt|Luce|Perry|1949}}, who used complete subgraphs to model [[clique]]s (groups of people who all know each other) in [[social network]]s. The same definition was used by {{harvtxt|Festinger|1949}} in an article using less technical terms. Both works deal with uncovering cliques in a social network using matrices. For continued efforts to model social cliques graph-theoretically, see e.g. {{harvtxt|Alba|1973}}, {{harvtxt|Peay|1974}}, and {{harvtxt|Doreian|Woodard|1994}}. − The word "clique", in its graph-theoretic usage, arose from the work of , who used complete subgraphs to model cliques (groups of people who all know each other) in social networks. The same definition was used by in an article using less technical terms. Both works deal with uncovering cliques in a social network using matrices. For continued efforts to model social cliques graph-theoretically, see e.g. , , and .+ + − “团clique”一词在图形理论上的使用，来源于Luce＆Perry（1949）的研究《A method of matrix analysis of group structure》，他们通过完全子图对社交网络中的集团（彼此认识的人群）进行建模。之后Festinger（1949）在论文The analysis of sociograms using matrix algebra《使用矩阵代数的社会图分析》中以较少的术语进行了相同的定义。这两部作品都通过使用矩阵处理社交网络中的团问题。之后，Alba（1973），Peay（1974）和Doreian＆Woodard（1994）以图理论为基础对社交团体继续进行了图形化建模。 + − Many different problems from [[bioinformatics]] have been modeled using cliques. For instance, {{harvtxt|Ben-Dor|Shamir|Yakhini|1999}} model the problem of clustering [[gene expression]] data as one of finding the minimum number of changes needed to transform a graph describing the data into a graph formed as the disjoint union of cliques; {{harvtxt|Tanay|Sharan|Shamir|2002}} discuss a similar [[biclustering]] problem for expression data in which the clusters are required to be cliques. {{harvtxt|Sugihara|1984}} uses cliques to model [[ecological niche]]s in [[food chain|food webs]]. {{harvtxt|Day|Sankoff|1986}} describe the problem of inferring [[evolutionary tree]]s as one of finding maximum cliques in a graph that has as its vertices characteristics of the species, where two vertices share an edge if there exists a [[perfect phylogeny]] combining those two characters. {{harvtxt|Samudrala|Moult|1998}} model [[protein structure prediction]] as a problem of finding cliques in a graph whose vertices represent positions of subunits of the protein. And by searching for cliques in a [[protein-protein interaction]] network, {{harvtxt|Spirin|Mirny|2003}} found clusters of proteins that interact closely with each other and have few interactions with proteins outside the cluster. [[Power graph analysis]] is a method for simplifying complex biological networks by finding cliques and related structures in these networks.+ − Many different problems from bioinformatics have been modeled using cliques. For instance, model the problem of clustering gene expression data as one of finding the minimum number of changes needed to transform a graph describing the data into a graph formed as the disjoint union of cliques; discuss a similar biclustering problem for expression data in which the clusters are required to be cliques. uses cliques to model ecological niches in food webs. describe the problem of inferring evolutionary trees as one of finding maximum cliques in a graph that has as its vertices characteristics of the species, where two vertices share an edge if there exists a perfect phylogeny combining those two characters. model protein structure prediction as a problem of finding cliques in a graph whose vertices represent positions of subunits of the protein. And by searching for cliques in a protein-protein interaction network, found clusters of proteins that interact closely with each other and have few interactions with proteins outside the cluster. Power graph analysis is a method for simplifying complex biological networks by finding cliques and related structures in these networks. 第203行：
第112行： + − In [[electrical engineering]], {{harvtxt|Prihar|1956}} uses cliques to analyze communications networks, and {{harvtxt|Paull|Unger|1959}} use them to design efficient circuits for computing partially specified Boolean functions. Cliques have also been used in [[automatic test pattern generation]]: a large clique in an incompatibility graph of possible faults provides a lower bound on the size of a test set.<ref>{{harvtxt|Hamzaoglu|Patel|1998}}.</ref> {{harvtxt|Cong|Smith|1993}} describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits. − − In electrical engineering, uses cliques to analyze communications networks, and use them to design efficient circuits for computing partially specified Boolean functions. Cliques have also been used in automatic test pattern generation: a large clique in an incompatibility graph of possible faults provides a lower bound on the size of a test set. describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits. − − 在电气工程中，Prihar（1956）使用团来分析通信网络，Paull＆Unger（1959）使用它们来设计有效的电路，以计算部分指定的布尔函数。团也已用于自动测试模式生成：不兼容图中可能出现故障的大团为测试集的大小提供了下限。<ref>{{harvtxt|Hamzaoglu|Patel|1998}}.</ref>Cong＆Smith（1993）描述了团在划分电子电路分层中的应用。 − − − − In [[chemistry]], {{harvtxt|Rhodes|Willett|Calvet|Dunbar|2003}} use cliques to describe chemicals in a [[chemical database]] that have a high degree of similarity with a target structure. {{harvtxt|Kuhl|Crippen|Friesen|1983}} use cliques to model the positions in which two chemicals will bind to each other. − − In chemistry, use cliques to describe chemicals in a chemical database that have a high degree of similarity with a target structure. use cliques to model the positions in which two chemicals will bind to each other. − − == See also 其他参考资料 == − + − * [[Clique game 团游戏]] − − − − − − {{reflist}} − − − − == References 参考文献 == 第243行：
第129行： − − − | last1 = Chang | first1 = Maw-Shang − − 1 = Chang | first1 = Maw-Shang − − | last2 = Kloks | first2 = Ton − − | last2 = Kloks | first2 = Ton − − − − | last3 = Lee | first3 = Chuan-Min − − 3 = Lee | first3 = Chuan-Min − − − | contribution = Maximum clique transversals − − | 贡献 = 最大团横截 − − | doi = 10.1007/3-540-45477-2_5 − − − | doi = 10.1007/3-540-45477-2 _ 5 − − − | mr = 1905299 − − 1905299先生 − − | pages = 32–43 − − − | 页数 = 32-43 − − − | publisher = Springer, Berlin − − | publisher = Springer，Berlin − − | series = Lecture Notes in Comput. Sci. − − − | 系列 = 计算机中的课堂讲稿。科学。 − − | title = Graph-theoretic concepts in computer science (Boltenhagen, 2001) − − − | title = 计算机科学中的图论概念(Boltenhagen，2001) − − | volume = 2204 − − − 2204 − − − | year = 2001| isbn = 978-3-540-42707-0 − − | year = 2001 | isbn = 978-3-540-42707-0 − − }}. − − }}. − 第333行：
第154行： − − − | last1 = Graham − − 1 = Graham − − − | first1 = R. − − 1 = r. − − − | author1-link = Ronald Graham − − | author1-link = Ronald Graham − − − | last2 = Rothschild − − | last2 = Rothschild − − − | first2 = B. − − 2 = b. − − | last3 = Spencer − − − 3 = Spencer − − | first3 = J. H. − − − 3 = j. h. − − − | author3-link = Joel Spencer − − | author3-link = Joel Spencer − − | location = New York − − − | 地点: 纽约 − − − | publisher = John Wiley and Sons − − 约翰威利父子出版社 − − | title = Ramsey Theory − − − 拉姆齐理论 − − − | year = 1990 − − 1990年 − − | isbn = 978-0-471-50046-9 − − − | isbn = 978-0-471-50046-9 − − − | url-access = registration − − | url-access = registration − − − | url = https://archive.org/details/ramseytheory0000grah − − Https://archive.org/details/ramseytheory0000grah − − }}. − − }}. − 第439行：
第180行： − − − | last1 = Luce | first1 = R. Duncan | author1-link = R. Duncan Luce − − 1 = Luce | first1 = r. Duncan | author1-link = r. Duncan Luce − − | last2 = Perry | first2 = Albert D. − − − 2 = Perry | first2 = Albert d. − − − | title = A method of matrix analysis of group structure − − | title = 群结构的矩阵分析方法 − − − | journal = Psychometrika | volume = 14 | issue = 2 | year = 1949 − − 14 | issue = 2 | year = 1949 − − + − − − − − | pmid = 18152948}}. − − | pmid = 18152948}}. − − 18152948}. − − − | last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L. − − − 1 = Moon | first1 = j. w. | author2-link = Leo Moser | last2 = Moser | first2 = l. − − | title = On cliques in graphs − − + − | title = 关于图中的团 − − | journal = Israel J. Math. − − − − 以色列 j。数学。 − − − | volume = 3 − − 3 − − | year = 1965 − − − 1965年 − − − | pages = 23–28 − − 23-28页 − − + − | mr = 0182577 − − 0182577先生 − − − − | doi = 10.1007/BF02760024}}. − − 10.1007/BF02760024}. 第543行：
第213行： − − | last = Turán − − + − | last = Turán − − | first = Paul | authorlink = Pál Turán − − − − 第一 = Paul | authorlink = Pál Turán − − | year = 1941 − − − 1941年 − − − | title = On an extremal problem in graph theory − − | title = 关于图论中的一个极值问题 − − | journal = Matematikai és Fizikai Lapok − − | journal = Matematikai és Fizikai Lapok − − − − | volume = 48 − − 48 − − + − | pages = 436–452 − − | 页数 = 436-452 − − | language = Hungarian − − | language = Hungarian − − − − − }} − − }} − − == External links 相关链接 ==+ − *{{MathWorld|title=Clique|urlname=Clique}} − *{{MathWorld|title=团|urlname=Clique}} − + − *{{MathWorld|title=Clique Number|urlname=CliqueNumber}} − *{{MathWorld|title=团数|urlname=CliqueNumber}} − − − [[Category:Graph theory objects]] − − Category:Graph theory objects − − 范畴: 图论对象 − − <noinclude> − − <small>This page was moved from [[wikipedia:en:Clique (graph theory)]]. Its edit history can be viewed at [[团（图论）/edithistory]]</small></noinclude> − − [[Category:待整理页面]]
无编辑摘要
{{#seo:
|keywords=无向图，顶点，图论
|description=无向图中顶点的子集，使得一个团中每两个不同的顶点必定相邻
}}
[[文件:VR complex.svg|缩略图|
[[文件:VR complex.svg|缩略图|
]]
]]
在图论的数学领域中，'''团 Clique'''是无向图中顶点的子集，使得一个团中每两个不同的顶点必定相邻。也就是说，其导出子图是完全图。团是图论的基本概念之一，可用于图形的构建和解决许多其他数学问题。而且，在计算机科学领域中也经常会涉及到团的研究：比如在一个给定规模的图中寻找团的存在就是一个NP-完全问题。尽管我们已经明确知道这个问题很难得以解决，但仍然有许多学者在研究用于寻找团的算法。
对完全子图的研究至少可以追溯到'''拉姆齐定理 Ramsey's theorem'''中的图论重组，由Erdős＆Szekeres（1935）在论文A combinatorial problem in geometry《几何组合问题》提出的。<ref>The earlier work by {{harvtxt|Kuratowski|1930}} characterizing [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subgraphs was originally phrased in topological rather than graph-theoretic terms.</ref>但实际上“团”一词是来自Luce＆Perry（1949）的论文《群结构矩阵分析的一种方法 A method of matrix analysis of group structure》，后者在社交网络中使用完全子图来对人群进行建模；该模型定义在这群人中，所有人是互相认识的。其实团这一概念在诸多科学领域中均有所应用，尤其是在生物信息学。
'''极大团 Maximal clique'''也是一个团，但是不能通过合并更多的相邻节点而进行扩张，换句话说，该团不可能被更大团的顶点集合所包含。有些学者将“极大团”定义为“团”，用其他完全子团的术语来重新定义“非极大团”。
图''G''中同样存在一个'''最大团 Maximum clique'''，使得其不存在更多顶点。另外，图''G''的团数''ω（G）''是该图最大团的顶点数。
图''G''的'''交叉数 Intersection number'''是该图中同时能覆盖所有连边的最少团数。
图''G''的'''团覆盖数 Clique cover number'''指的是能覆盖图''G''中所有顶点集''V''的最少团数。
一个图的''' 最大团横贯集Maximum clique transversal'''是其顶点的子集，其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。
作为团的对立面，'''独立集 Independent set'''是指图中两两互相不相邻的顶点集合。因此，每一个团都对应于补图中的独立集。集团覆盖问题涉及到寻找尽可能少的团，其中包括图中的每个顶点。
'''二元团 biclique'''是团的相关概念，指的是一个完全二分图。该图的二分维度指的是覆盖该图所有连边所需的最少二元团数。
== Mathematics 数学运算==
==数学运算==
有关团的数学结论包括以下内容。
有关团的数学结论包括以下内容。
* ''' 托兰定理 Turán's theorem '''在''' 稠密图Dense graph'''中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过<math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math>个边的图形都必然含一个三顶点团。
* '''<font color="#ff8000"> 托兰定理 Turán's theorem </font>'''在'''<font color="#ff8000"> 稠密图Dense graph</font>'''中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过<math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math>个边的图形都必然含一个三顶点团。
* 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3<sup>''n''</sup>个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3<sup>''n''</sup>个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
* Erdős–Faber–Lovász猜想是另一个未经证实的陈述，同样认为图的着色与团相关。
* Erdős–Faber–Lovász猜想是另一个未经证实的陈述，同样认为图的着色与团相关。
由"团"的特性来定义和区分几种重要的"图"类别：
由"团"的特性来定义和区分几种重要的"图"类别：
* ''' 聚类图 Cluster graph'''是图的一种特例，其连接的组成部分是团。
* ''' 框图 Block graph'''是图的一种特例，其双连通的部分是团。
* ''' 弦图 Chordal graph'''是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。
* ''' 余图 Cograph'''是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。
* '''区间图 Interval graph'''是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。
* '''线图 Line graph'''是图的一种特例，其连边可以被边不相交的团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。
* '''完美图 Perfect graph'''是图的一种特例，其导出子图的色数等于此导出子图的团数。
* '''分裂图 Split graph'''是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。
* '''三角形无关图 Triangle-free graph'''是图的一种特例，除了顶点和连边之外，该图不含任何团。
此外，还有许多其他数学结构与图论的"团"有关。它们包括，
* 图G的'''团复形 Clique complex'''属于'''抽象复形 Abstract simplicial complex'''，其中图G的每个团都为单纯形。
* '''单纯形图 Simplex graph'''可记为无向图''κ（G）''，它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。它是中线图的一个示例，并且与图中团的中位数相关联：三个团A，B和C的中位团m（A，B，C），其顶点至少属于团A，B和C中的两个。
* '''团相加 Clique-sum'''指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
* '''团宽度 Clique-width'''是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。即通过不相交的并集构建图形所需的不同顶点标签的最小数量，通过以下操作建立：
# 将两个已标记的图拆开，使其不相交；
# 将两个已标记的图拆开，使其不相交；
# 重新标记；
# 重新标记；
# 根据给定的标记，连接所有成对顶点。
# 根据给定的标记，连接所有成对顶点。
团宽度为1的图就是团的不相交并集。
* 图的交叉数Intersection number指的是能覆盖图所有连边所需的最小团数。
* 图G的团图 Clique graph指的是该图的极大团的交叉图。主要为了展示图G的团结构。
从概念上来说，完全子图与完全图细分，以及完全图子式密切相关。尤其是Kuratowski定理和Wagner定理，它们就是通过禁用完全图、完全二分图细分和完全二分图子式来描述平面图特征的。
从概念上来说，完全子图与完全图细分，以及完全图子式密切相关。尤其是Kuratowski定理和Wagner定理，它们就是通过禁用完全图、完全二分图细分和完全二分图子式来描述平面图特征的。
== 计算机科学==
在计算机科学中，团问题指的是在给定图中查找最大团或所有团的计算问题。它是是Karp提出的21个NP-完全问题之一。它也是固定参数难求解问题，甚至难以获得近似值。尽管如此，目前专业人士已经开发了诸多用于计算团的算法，包括可以在指数时间内求解的例如Bron–Kerbosch算法，以及在多项式时间内专门求解图族（例如平面图或完美图）这类问题的算法。
== 应用 ==
“团clique”一词在图形理论上的使用，来源于Luce＆Perry（1949）的研究《A method of matrix analysis of group structure》，他们通过完全子图对社交网络中的集团（彼此认识的人群）进行建模。之后Festinger（1949）在论文《使用矩阵代数的社会图分析 The analysis of sociograms using matrix algebra》中以较少的术语进行了相同的定义。这两部作品都通过使用矩阵处理社交网络中的团问题。之后，Alba（1973），Peay（1974）和Doreian＆Woodard（1994）以图理论为基础对社交团体继续进行了图形化建模。
在生物信息学领域，诸多不同问题都已经通过“团”来实现建模。例如，Ben-Dor，Shamir和Yakhini（1999）对基因表达数据的聚类问题进行了建模，通过将数据描述的图转换为含有不相交团的图，并在转变过程中找寻最小改变量。另外，Tanay，Sharan＆Shamir（2002）讨论了一个类似的表达数据的双聚类问题，在该问题中，群集被描述为“团”。Sugihara（1984）使用“团”对食物网中的生态位进行建模。Day＆Sankoff（1986）将推论进化树的问题描述为在具有该物种顶点特征的图形中找到最大团的问题之一，如果存在一个物种能将这两个特征完美结合，则两个顶点共享一条边。Samudrala＆Moult（1998）将蛋白质结构预测模型化为，
在生物信息学领域，诸多不同问题都已经通过“团”来实现建模。例如，Ben-Dor，Shamir和Yakhini（1999）对基因表达数据的聚类问题进行了建模，通过将数据描述的图转换为含有不相交团的图，并在转变过程中找寻最小改变量。另外，Tanay，Sharan＆Shamir（2002）讨论了一个类似的表达数据的双聚类问题，在该问题中，群集被描述为“团”。Sugihara（1984）使用“团”对食物网中的生态位进行建模。Day＆Sankoff（1986）将推论进化树的问题描述为在具有该物种顶点特征的图形中找到最大团的问题之一，如果存在一个物种能将这两个特征完美结合，则两个顶点共享一条边。Samudrala＆Moult（1998）将蛋白质结构预测模型化为，
在电气工程中，Prihar（1956）使用团来分析通信网络，Paull＆Unger（1959）使用它们来设计有效的电路，以计算部分指定的布尔函数。团也已用于自动测试模式生成：不兼容图中可能出现故障的大团为测试集的大小提供了下限。Cong＆Smith（1993）描述了团在划分电子电路分层中的应用。
在化学上，Rhodes等学者（2003年）使用团来描述化学数据库中与目标结构具有高度相似性的化学物质。Kuhl，Crippen＆Friesen（1983）使用团对两种化学物质相互结合的位置进行建模。
在化学上，Rhodes等学者（2003年）使用团来描述化学数据库中与目标结构具有高度相似性的化学物质。Kuhl，Crippen＆Friesen（1983）使用团对两种化学物质相互结合的位置进行建模。
== 参考文献 ==
== Notes 备注==
{{refbegin}}
{{refbegin}}
*{{citation
*{{citation
| last1 = Chang | first1 = Maw-Shang
| last1 = Chang | first1 = Maw-Shang
| last2 = Kloks | first2 = Ton
| last2 = Kloks | first2 = Ton
| last3 = Lee | first3 = Chuan-Min
| last3 = Lee | first3 = Chuan-Min
| contribution = Maximum clique transversals
| contribution = Maximum clique transversals
| doi = 10.1007/3-540-45477-2_5
| doi = 10.1007/3-540-45477-2_5
| mr = 1905299
| mr = 1905299
| pages = 32–43
| pages = 32–43
| publisher = Springer, Berlin
| publisher = Springer, Berlin
| series = Lecture Notes in Comput. Sci.
| series = Lecture Notes in Comput. Sci.
| title = Graph-theoretic concepts in computer science (Boltenhagen, 2001)
| title = Graph-theoretic concepts in computer science (Boltenhagen, 2001)
| volume = 2204
| volume = 2204
| year = 2001| isbn = 978-3-540-42707-0
| year = 2001| isbn = 978-3-540-42707-0
}}.
}}.
*{{citation
*{{citation
| last1 = Graham
| last1 = Graham
| first1 = R.
| first1 = R.
| author1-link = Ronald Graham
| author1-link = Ronald Graham
| last2 = Rothschild
| last2 = Rothschild
| first2 = B.
| first2 = B.
| last3 = Spencer
| last3 = Spencer
| first3 = J. H.
| first3 = J. H.
| author3-link = Joel Spencer
| author3-link = Joel Spencer
| location = New York
| location = New York
| publisher = John Wiley and Sons
| publisher = John Wiley and Sons
| title = Ramsey Theory
| title = Ramsey Theory
| year = 1990
| year = 1990
| isbn = 978-0-471-50046-9
| isbn = 978-0-471-50046-9
| url-access = registration
| url-access = registration
| url = https://archive.org/details/ramseytheory0000grah
| url = https://archive.org/details/ramseytheory0000grah
}}.
}}.
*{{citation
*{{citation
| last1 = Luce | first1 = R. Duncan | author1-link = R. Duncan Luce
| last1 = Luce | first1 = R. Duncan | author1-link = R. Duncan Luce
| last2 = Perry | first2 = Albert D.
| last2 = Perry | first2 = Albert D.
| title = A method of matrix analysis of group structure
| title = A method of matrix analysis of group structure
| journal = Psychometrika | volume = 14 | issue = 2 | year = 1949
| journal = Psychometrika | volume = 14 | issue = 2 | year = 1949
| pages = 95–116 | doi = 10.1007/BF02289146
| pages = 95–116 | doi = 10.1007/BF02289146
| pmid = 18152948| hdl = 10.1007/BF02289146 | s2cid = 16186758 | hdl-access = free }}.
| pages = 95–116 | doi = 10.1007/BF02289146
| pages = 95-116 | doi = 10.1007/BF02289146
*{{citation
*{{citation
| last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L.
| last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L.
| title = On cliques in graphs
| title = On cliques in graphs
| journal = [[Israel Journal of Mathematics]]
| journal = Israel J. Math.
| volume = 3
| volume = 3
| year = 1965
| year = 1965
| pages = 23–28
| pages = 23–28
| mr = 0182577
| mr = 0182577
| doi = 10.1007/BF02760024 | doi-access=free}}.
| doi = 10.1007/BF02760024}}.
*{{citation |first1=M. C. |last1=Paull |first2=S. H. |last2=Unger |title=Minimizing the number of states in incompletely specified sequential switching functions |journal=IRE Transactions on Electronic Computers |volume=EC-8 |issue=3 |year=1959 |pages=356–367 |doi=10.1109/TEC.1959.5222697}}.
*{{citation |first1=M. C. |last1=Paull |first2=S. H. |last2=Unger |title=Minimizing the number of states in incompletely specified sequential switching functions |journal=IRE Transactions on Electronic Computers |volume=EC-8 |issue=3 |year=1959 |pages=356–367 |doi=10.1109/TEC.1959.5222697}}.
*{{citation
*{{citation
| last = Turán
| last = Turán
| first = Paul | author-link = Pál Turán
| first = Paul | authorlink = Pál Turán
| year = 1941
| year = 1941
| title = On an extremal problem in graph theory
| title = On an extremal problem in graph theory
| journal = Matematikai és Fizikai Lapok
| journal = Matematikai és Fizikai Lapok
| volume = 48
| volume = 48
| pages = 436–452
| pages = 436–452
| language = hu
| language = 匈牙利语
}}
}}
{{refend}}
{{refend}}
[[Category:图论对象]]
此词条由Jie初步翻译，由Flipped审校。