| Clique (graph Theory) |
Article Index for Clique |
Information AboutClique (graph Theory) |
|
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. Alternatively, a clique is a graph in which every vertex is connected to every other vertex in the graph. 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 . The term presumably comes from the idea that if the vertices represent people and the edges represent the relation 'knows', then everyone knows everyone else, thus forming a Clique . SEE ALSO |
|
|