In graph theory, a clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph). The size of a clique is the number of vertices it contains.
Finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete.
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 term presumably comes from the idea that, if the vertices represent people and the edges represent the relation 'knows', then everyone knows everyone else, thus forming a clique.
The clique number ω(G) of a graph G is the order of a largest clique in G.
Contents |
Notes
See also
- Glossary of graph theory
- Maximum common subgraph isomorphism problem
- Maximal clique
- Clique complex, an abstract simplicial complex X(G) with a simplex for every clique in a graph G
- Simplex graph, an undirected graph κ(G) with a vertex for every clique in a graph G
References
- Godsil, Chris; Royle, Gordon (2004). Algebraic graph theory. New York: Springer. ISBN 0-387-95220-9.
- Weisstein, Eric W., "Clique" from MathWorld.
- Weisstein, Eric W., "Clique Number" from MathWorld.
External links
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)




