To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Clique (graph theory)

In the mathematical area of graph theory, a clique (/ˈklk/ or /ˈklɪk/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph ${\displaystyle G}$ is an induced subgraph of ${\displaystyle G}$ that 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 Erdős & Szekeres (1935),[1] the term clique comes from Luce & Perry (1949), 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.

• 1/5
Views:
54 826
391
13 385
17 890
2 786
• What is a Clique? | Graph Theory, Cliques
• What are Clique Graphs? [Graph Theory Tutorial]
• Clique in Graph Theory in HINDI | Independent Set in graph theory in HINDI | Discrete Mathematics
• What is a Maximal Clique? | Graph Theory, Cliques, Maximal Cliques
• What are the Maximum and Maximal Cliques of this Graph? | Graph Theory

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

The intersection number of G is the smallest number of cliques that together cover all edges of G.

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.

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.[2]

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.

Mathematics

Mathematical results concerning cliques include the following.

Several important classes of graphs may be defined or characterized by their cliques:

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.[5]
• 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.

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.[6] 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 Luce & Perry (1949), who used complete subgraphs to model cliques (groups of people who all know each other) in social networks. The same definition was used by 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. Alba (1973), Peay (1974), and Doreian & Woodard (1994).

Many different problems from bioinformatics have been modeled using cliques. For instance, 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; Tanay, Sharan & Shamir (2002) discuss a similar biclustering problem for expression data in which the clusters are required to be cliques. Sugihara (1984) uses cliques to model ecological niches in food webs. Day & Sankoff (1986) 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. 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, 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, Prihar (1956) uses cliques to analyze communications networks, and 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.[7] Cong & Smith (1993) describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits.

In chemistry, Rhodes et al. (2003) use cliques to describe chemicals in a chemical database that have a high degree of similarity with a target structure. Kuhl, Crippen & Friesen (1983) use cliques to model the positions in which two chemicals will bind to each other.

Notes

1. ^ The earlier work by Kuratowski (1930) characterizing planar graphs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.
2. ^
3. ^
4. ^
5. ^ Barthélemy, Leclerc & Monjardet (1986), page 200.
6. ^
7. ^

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, archived (PDF) from the original on 2011-05-03, retrieved 2009-12-14.
• 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, S2CID 6092438.
• Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), "Clustering gene expression patterns.", Journal of Computational Biology, 6 (3–4): 281–297, CiteSeerX 10.1.1.34.5341, doi:10.1089/106652799318274, PMID 10582567.
• Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", Graph-theoretic concepts in computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, pp. 32–43, doi:10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, MR 1905299.
• Cong, J.; Smith, M. (1993), "A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design", Proc. 30th International Design Automation Conference, pp. 755–760, CiteSeerX 10.1.1.32.735, doi:10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
• 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.
• Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry" (PDF), Compositio Mathematica, 2: 463–470, archived (PDF) from the original on 2020-05-22, retrieved 2009-12-19.
• Festinger, Leon (1949), "The analysis of sociograms using matrix algebra", Human Relations, 2 (2): 153–158, doi:10.1177/001872674900200205, S2CID 143609308.
• Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory, New York: John Wiley and Sons, ISBN 978-0-471-50046-9.
• 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, S2CID 12258606.
• Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-13.
• 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, S2CID 122923018.
• Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en Topologie" (PDF), Fundamenta Mathematicae (in French), 15: 271–283, doi:10.4064/fm-15-1-271-283, archived (PDF) from the original on 2018-07-23, retrieved 2009-12-19.
• Luce, R. Duncan; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika, 14 (2): 95–116, doi:10.1007/BF02289146, hdl:10.1007/BF02289146, PMID 18152948, S2CID 16186758.
• Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577.
• 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.
• Peay, Edmund R. (1974), "Hierarchical clique structures", Sociometry, 37 (1): 54–65, doi:10.2307/2786466, JSTOR 2786466.
• Prihar, Z. (1956), "Topological properties of telecommunications networks", Proceedings of the IRE, 44 (7): 927–933, doi:10.1109/JRPROC.1956.275149, S2CID 51654879.
• 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.
• Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, CiteSeerX 10.1.1.64.8918, doi:10.1006/jmbi.1998.1689, PMID 9636717.
• Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
• Sugihara, George (1984), "Graph theory, homology and food webs", in Levin, Simon A. (ed.), Population Biology, Proc. Symp. Appl. Math., vol. 30, pp. 83–101.
• Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), "Discovering statistically significant biclusters in gene expression data", Bioinformatics, 18 (Suppl. 1): S136–S144, doi:10.1093/bioinformatics/18.suppl_1.S136, PMID 12169541.
• Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in Hungarian), 48: 436–452
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.