Clique (graph theory)
From Wikipedia, the free encyclopedia
In graph theory, a clique in an undirected graph G is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by V is a complete graph. 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.
[edit] See also
- Solving the Maximum common subgraph isomorphism problem
