This problem is one of the most familiar problem in computer science. The maximal complete subgraph of a graph G is a clique. The size of the clique is the number of vertices in it. The max-clique problem is that finding the largest possible clique in the graph.
There is another definition for the clique. A clique is a set of vertices from the original graph G in which every vertex in the set have an edge with any other vertex in the set.
This is an optimisation problem. But it can be viewed in the angles of decision problem in the following way.
Does the graph can have a clique of size 6 ---NO
Does the graph can have a clique of size 5 ---NO
Does the graph can have a clique of size 4 ---yes
Thus the maximum clique has the size of 4.
Similarly satisfiablity problem, Node cover problem
etc are viewed in this way.
There is another definition for the clique. A clique is a set of vertices from the original graph G in which every vertex in the set have an edge with any other vertex in the set.This is an optimisation problem. But it can be viewed in the angles of decision problem in the following way.
Does the graph can have a clique of size 6 ---NO
Does the graph can have a clique of size 5 ---NO
Does the graph can have a clique of size 4 ---yes
Thus the maximum clique has the size of 4.
Similarly satisfiablity problem, Node cover problem
etc are viewed in this way.
No comments:
Post a Comment