Clique (graph theory)
From Free net 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.
Unfortunately finding cliques within a graph can be a hard problem. Finding a clique of a given size in a graph (the clique problem), for example, 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
he:גרף מלא de:Knotenüberdeckungen, Cliquen und stabile Mengen pl:Klika (teoria grafów)