This slideshow introduces and explains the "Clique" Problem.
We start with some definitions and background.
A Clique is complete graph i.e. a graph where each node is connected to every other node by at least one edge.
Example of a clique:
A
B
C
D
E
F
If in a graph G there exists a complete subgraph of k nodes, G is said to contain a k-clique.
For example, the following graph contains a 3-clique. (Actually, there is more than one.)
1
2
3
4
5
6
Any clique with the largest number of vertices in a graph G is called a Maximum Clique in G.
For example, the Maximum Clique in this graph is a 4-clique.
The Clique Problem can be defined as either of the following:
Given a graph G=(V,E), find the Maximum Clique in G. This is the optimization form of the problem.
Or
Given a graph G=(V,E), and a number k, does G contain a Clique of size ≥k ? This is the decision form of the problem.
a
b
c
d
e
f
g
h
i
j
In the graph below does there exist a clique of size ≥5?
No
In the graph below does there exist a clique of size ≥4?
Yes
