|
|
|
|
|
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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|