Clique (graph theory)
|
|
Complete_graph_K5.png
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.
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 |V′|=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 complement graph.de:Vollständiger Graph pl:Klika (teoria grafów)