
In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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, a clique of a graph
is an
induced subgraph of
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
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
: the task of finding whether there is a clique of a given size in a
graph (the
clique problem) is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
, 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
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...
by , the term ''clique'' comes from , who used complete subgraphs in
social network
A social network is a social structure consisting of a set of social actors (such as individuals or organizations), networks of Dyad (sociology), dyadic ties, and other Social relation, social interactions between actors. The social network per ...
s 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
Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
.
Definitions
A clique, , in an
undirected graph 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 induced by 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, , is a clique, such that there is no clique with more vertices. Moreover, the clique number of a graph is the number of vertices in a maximum clique in .
The
intersection number
In mathematics, and especially in algebraic geometry, the intersection number generalizes the intuitive notion of counting the number of times two curves intersect to higher dimensions, multiple (more than 2) curves, and accounting properly for ta ...
of is the smallest number of cliques that together cover all edges of .
The clique cover number of a graph is the smallest number of cliques of whose union covers the set of vertices 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.
The opposite of a clique is an
independent set, in the sense that every clique corresponds to an independent set in the
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
. 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.
*
Turán's theorem gives a
lower bound on the size of a clique in
dense graphs. If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with
vertices and more than
edges must contain a three-vertex clique.
*
Ramsey's theorem states that every graph or its
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
contains a clique with at least a logarithmic number of vertices.
* According to a result of , a graph with 3''n'' vertices can have at most 3
''n'' maximal cliques. The graphs meeting this bound are the Moon–Moser graphs ''K''
3,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 relates graph coloring to cliques.
* The
Erdős–Hajnal conjecture states that families of graphs defined by
forbidden graph characterization have either large cliques or large
cocliques.
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
In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
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.
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
* The
clique complex of a graph ''G'' is an
abstract simplicial complex
In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely c ...
''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''.
* 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
In mathematics, and especially in algebraic geometry, the intersection number generalizes the intuitive notion of counting the number of times two curves intersect to higher dimensions, multiple (more than 2) curves, and accounting properly for ta ...
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
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a Glossary of graph theory#Su ...
and
Wagner's theorem characterize
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s by forbidden complete and
complete bipartite subdivisions and minors, respectively.
Computer science
In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the
clique problem is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
, one of
Karp's 21 NP-complete problems. It is also
fixed-parameter intractable, and
hard to approximate. Nevertheless, many
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s 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 , who used complete subgraphs to model
cliques (groups of people who all know each other) in
social network
A social network is a social structure consisting of a set of social actors (such as individuals or organizations), networks of Dyad (sociology), dyadic ties, and other Social relation, social interactions between actors. The social network per ...
s. 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
Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
have been modeled using cliques. For instance, model the problem of clustering
gene expression
Gene expression is the process (including its Regulation of gene expression, regulation) by which information from a gene is used in the synthesis of a functional gene product that enables it to produce end products, proteins or non-coding RNA, ...
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 niche
In ecology, a niche is the match of a species to a specific environmental condition.
Three variants of ecological niche are described by
It describes how an organism or population responds to the distribution of Resource (biology), resources an ...
s 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
Protein structure prediction is the inference of the three-dimensional structure of a protein from its amino acid sequence—that is, the prediction of its Protein secondary structure, secondary and Protein tertiary structure, tertiary structure ...
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
Protein–protein interactions (PPIs) are physical contacts of high specificity established between two or more protein molecules as a result of biochemical events steered by interactions that include electrostatic forces, hydrogen bonding and t ...
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
Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems that use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...
, 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
Chemistry is the scientific study of the properties and behavior of matter. It is a physical science within the natural sciences that studies the chemical elements that make up matter and chemical compound, compounds made of atoms, molecules a ...
, 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
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*
External links
*
*{{MathWorld, title=Clique Number, urlname=CliqueNumber, mode=cs2
Graph theory objects