Science Fair Project Encyclopedia
Clique (graph theory)
In graph theory, a clique in a undirected graph G, is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. Additionally, this means that a clique is simply a complete subgraph of G. The size of a clique is the number of vertices it contains.
The clique problem refers to the problem of finding the largest clique in any graph G. This problem is NP-complete, and as such, many consider that it is unlikely that an efficient algorithm for finding the largest clique of a graph exists.
A k-clique is a clique of size k. Therefore, the k-clique problem refers to the problem of finding a clique of size k, i.e. a complete subgraph G′(V′,E′) of G with |E′|=k. A k-clique can be found using a brute-force algorithm in O(nk) time.
The opposite of a clique is an independent set. If we already know that the independent set problem is NP-complete, then it is easy to prove, as the size of the largest clique is the same as the size of the largest independent set in the inverse graph.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details