更改

==Definitions==

== Definitions 定义 ==

A '''clique''', ''C'', in an [[undirected graph]] {{nowrap|''G'' {{=}} (''V'', ''E'')}} is a subset of the [[Vertex (graph theory)|vertices]], {{nowrap|''C'' ⊆ ''V''}}, 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]] {{nowrap|''G'' {{=}} (''V'', ''E'')}} is a subset of the [[Vertex (graph theory)|vertices]], {{nowrap|''C'' ⊆ ''V''}}, 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.

==Computer science==

== Computer science 计算机科学==

{{main|Clique problem}}

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

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

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 .

Many different problems from [[bioinformatics]] have been modeled using cliques.

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.

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.

在生物信息学领域，诸多不同问题都已经通过“团”来实现建模。例如，Ben-Dor，Shamir和Yakhini（1999）对基因表达数据的聚类问题进行了建模，通过将数据描述的图转换为含有不相交团的图，并在转变过程中找寻最小改变量。另外，Tanay，Sharan＆Shamir（2002）讨论了一个类似的表达数据的双聚类问题，在该问题中，群集被描述为“团”。Sugihara（1984）使用“团”对食物网中的生态位进行建模。Day＆Sankoff（1986）将推论进化树的问题描述为在具有该物种顶点特征的图形中找到最大团的问题之一，如果存在一个可能能将这两个特征完美结合，则两个顶点共享一条边。Samudrala＆Moult（1998）将蛋白质结构预测模型化为在图中顶点表示蛋白质亚基位置的图中发现团簇的问题。通过在蛋白质-蛋白质相互作用网络中寻找群体，Spirin＆Mirny（2003）发现了彼此紧密相互作用的蛋白质簇，并且与簇外部的蛋白质几乎没有相互作用。功率图分析是一种通过在这些网络中查找团簇和相关结构来简化复杂生物网络的方法。

 

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.

 

 

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

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

== See also 其他参考资料 ==

* [[Clique game]]

* [[Clique game 团游戏]]

==Notes==

== Notes 备注==

{{reflist}}

{{reflist}}

==References==

== References 参考文献 ==

{{refbegin}}

{{refbegin}}

==External links==

== External links 相关链接 ==

*{{MathWorld|title=Clique|urlname=Clique}}

*{{MathWorld|title=Clique|urlname=Clique}}

*{{MathWorld|title=Clique Number|urlname=CliqueNumber}}

*{{MathWorld|title=Clique Number|urlname=CliqueNumber}}