# 团（图论）

• 23 × 1-vertex cliques (the vertices), 23个单顶点团（顶点） • 42 × 2-vertex cliques (the edges), 42个双顶点团（边） • 19 × 3-vertex cliques (light and dark blue triangles), 19个三顶点团（浅色和深色的三角形） • 2 × 4-vertex cliques (dark blue areas).2个四顶点团（深色区域） The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4. 11个浅蓝色三角形（三顶点团）为极大团。2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。

In the mathematical area of graph theory, a clique (模板:IPAc-en or 模板:IPAc-en) 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.

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.

Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by 脚本错误：没有“Footnotes”这个模块。,[1] the term clique comes from 脚本错误：没有“Footnotes”这个模块。, 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.

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.

## Definitions 定义

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, CV, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.

A clique, C, in an undirected graph (V, E)}} is a subset of the vertices, , such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.

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.

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中同样存在一个 最大团Maximum clique，使得其不存在更多顶点。另外，图G的团数ω（G）是该图最大团的顶点数。

The 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 交叉数Intersection number是该图中同时能覆盖所有连边的最少团数。

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 团覆盖数Clique cover number指的是能覆盖图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

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.

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.

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.

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.

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.

## Mathematics 数学运算

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 graphs.模板:Sfnp If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with $\displaystyle{ n }$ vertices and more than $\displaystyle{ \scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil }$ 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
• According to a result of 脚本错误：没有“Footnotes”这个模块。, a graph with 3n vertices can have at most 3n maximal cliques. The graphs meeting this bound are the Moon–Moser graphs K3,3,..., a special case of the Turán graphs arising as the extremal cases in Turán's theorem.
• Hadwiger's conjecture, still unproven, relates the size of the largest clique 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.
• 托兰定理 Turán's theorem 稠密图Dense graph中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过$\displaystyle{ \scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil }$个边的图形都必然含一个三顶点团。
• 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
• 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3n个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
• Erdős–Faber–Lovász猜想是另一个未经证实的陈述，同样认为图的着色与团相关。

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 components are cliques.
• A block graph is a graph whose biconnected components are cliques.
• A chordal graph is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the 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.
• 聚类图Cluster graph是图的一种特例，其连接的组成部分是团。
• 框图Block graph是图的一种特例，其双连通的部分是团。
• 弦图Chordal graph是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。
• 余图Cograph是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。
• 区间图Interval graph是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。
• 线图Line graph是图的一种特例，其连边可以被边不相交的团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。
• 完美图Perfect graph是图的一种特例，其导出子图的色数等于此导出子图的团数。
• 分裂图Split graph是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。
• 三角形无关图Triangle-free graph是图的一种特例，除了顶点和连边之外，该图不含任何团。

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.[3]
• 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 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的 团复形Clique complex属于 抽象复形Abstract simplicial complex，其中图G的每个团都为单纯形。
• 单纯形图Simplex graph可记为无向图κ（G），它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。它是中线图的一个示例，并且与图中团的中位数相关联：三个团A，B和C的中位团m（A，B，C），其顶点至少属于团A，B和C中的两个。[4]
• 团相加Clique-sum指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
• 团宽度Clique-width是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。即通过不相交的并集构建图形所需的不同顶点标签的最小数量，通过以下操作建立：
1. 将两个已标记的图拆开，使其不相交；
2. 重新标记；
3. 根据给定的标记，连接所有成对顶点。

• 图的 交叉数Intersection number指的是能覆盖图所有连边所需的最小团数。
• 图G的 团图Clique graph指的是该图的极大团的交叉图。主要为了展示图G的团结构。

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.

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 计算机科学

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 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.

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.

## Applications 应用

The word "clique", in its graph-theoretic usage, arose from the work of 脚本错误：没有“Footnotes”这个模块。, who used complete subgraphs to model cliques (groups of people who all know each other) in social networks. The same definition was used by 脚本错误：没有“Footnotes”这个模块。 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. 脚本错误：没有“Footnotes”这个模块。, 脚本错误：没有“Footnotes”这个模块。, and 脚本错误：没有“Footnotes”这个模块。.

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, 脚本错误：没有“Footnotes”这个模块。 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; 脚本错误：没有“Footnotes”这个模块。 discuss a similar biclustering problem for expression data in which the clusters are required to be cliques. 脚本错误：没有“Footnotes”这个模块。 uses cliques to model ecological niches in food webs. 脚本错误：没有“Footnotes”这个模块。 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. 脚本错误：没有“Footnotes”这个模块。 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, 脚本错误：没有“Footnotes”这个模块。 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.

In electrical engineering, 脚本错误：没有“Footnotes”这个模块。 uses cliques to analyze communications networks, and 脚本错误：没有“Footnotes”这个模块。 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.[5] 脚本错误：没有“Footnotes”这个模块。 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.

In chemistry, 脚本错误：没有“Footnotes”这个模块。 use cliques to describe chemicals in a chemical database that have a high degree of similarity with a target structure. 脚本错误：没有“Footnotes”这个模块。 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.

## Notes 备注

1. The earlier work by 脚本错误：没有“Footnotes”这个模块。 characterizing planar graphs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.
2. The earlier work by 脚本错误：没有“Footnotes”这个模块。 characterizing planar graphs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.
3. 脚本错误：没有“Footnotes”这个模块。, page 200.
4. 脚本错误：没有“Footnotes”这个模块。, page 200.
5. 脚本错误：没有“Footnotes”这个模块。.
6. 脚本错误：没有“Footnotes”这个模块。.

## References 参考文献

• Alba, Richard D. (1973), "A graph-theoretic definition of a sociometric clique" (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080/0022250X.1973.9989826.
• Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188.
• Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", 计算机科学中的图论概念(Boltenhagen，2001), Lecture Notes in Comput. Sci., 2204

2204, Springer，Berlin, pp. 32–43, doi:10.1007/3-540-45477-2 _ 5 Check |doi= value (help), ISBN 978-3-540-42707-0, MR [//www.ams.org/mathscinet-getitem?mr=1905299%0A%0A1905299%E5%85%88%E7%94%9F 1905299 1905299先生] Check |mr= value (help) Unknown parameter |贡献= ignored (help); Unknown parameter |页数= ignored (help); Unknown parameter |系列= ignored (help); line feed character in |mr= at position 8 (help); line feed character in |volume= at position 5 (help).

}}.

}}.

• Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
• Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks", Social Networks, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2.

2 = b.; Spencer 3 = Spencer, J. H. 3 = j. h. (1990

Https://archive.org/details/ramseytheory0000grah Ramsey Theory 拉姆齐理论] Check |url= value (help), New York: John Wiley and Sons

" ignored (help); line feed character in |first3= at position 6 (help); line feed character in |title= at position 14 (help); line feed character in |last3= at position 8 (help); line feed character in |last1= at position 7 (help); line feed character in |first2= at position 3 (help); line feed character in |first1= at position 3 (help); line feed character in |year= at position 5 (help); line feed character in |publisher= at position 20 (help); line feed character in |url= at position 49 (help); Check date values in: |year= (help).

}}.

}}.

• Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 978-1581130089.
• Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105.
| pmid = 18152948}}.


18152948}.

1965年), "关于图中的团", Israel J. Math. 以色列 j。数学。, 3

3: 23–28

23-28页, doi:10.1007/BF02760024, MR [//www.ams.org/mathscinet-getitem?mr=0182577+%0A%0A0182577%E5%85%88%E7%94%9F 0182577 0182577先生] Check |mr= value (help) line feed character in |mr= at position 9 (help); line feed character in |volume= at position 2 (help); line feed character in |year= at position 5 (help); line feed character in |journal= at position 16 (help); line feed character in |pages= at position 6 (help); Check date values in: |year= (help).

| doi = 10.1007/BF02760024}}.


10.1007/BF02760024}.

• Paull, M. C.; Unger, S. H. (1959), "Minimizing the number of states in incompletely specified sequential switching functions", IRE Transactions on Electronic Computers, EC-8 (3): 356–367, doi:10.1109/TEC.1959.5222697.
• Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
• Sugihara, George (1984), "Graph theory, homology and food webs", in Levin, Simon A. (ed.), Population Biology, Proc. Symp. Appl. Math., 30, pp. 83–101.

1941年), "关于图论中的一个极值问题", Matematikai és Fizikai Lapok (in 匈牙利语), 48

48: 436–452 Unknown parameter |页数= ignored (help); line feed character in |year= at position 5 (help); line feed character in |volume= at position 3 (help); Check date values in: |year= (help)CS1 maint: unrecognized language (link)

}}

}}