As yesterday, assume we have a simple graph G = (V,E). A clique is a collection of vertices U ⊆ V such that every pair of elements u ≠ v form an edge, i.e. {u, v} ∈ E. Notice that U is a clique if U is an independent set in the complement graph Gc = (V,Ec). A maximal clique is a maximal element (with respect to inclusion) in the collection of all cliques contained in G.
Our problem today is to calculate the size of a maximal clique in a given graph G. This number is called the clique number of G, and is usually denoted by ω(G).
Given a vertex v and a maximal clique C we have two options: either v is an element in C or v is not in C. In the first case, C is a clique in the subgraph induced by the vertex v and all of its neighbors. So, the clique number is 1 plus the clique number of the subgraph induced by the set of neighbors. In the second case, C is a clique of the graph obtained by removing v and all edges incident to v. So, we get a recursive formula that give us the clique number.
ω(G) = max (ω(G−v),1+ω(IndG(N(v))−v)) where
G − v is the graph obtained from G by removing v and all edges incident to v
IndG(N(v)) is the subgraph of G induced by the set of neighbors N(v) of v.
I will use list of edges to represent graphs. However, to accomodate graphs without edges, I will need loops.
(defparameter G
'((0 1) (1 2) (2 3) (2 4)
(0 0) (1 1) (2 2) (3 3) (4 4)))GBefore I present my implementation, I will need some helper functions. First, a function that deletes a collection of vertices
(defun delete-vertices (G vs)
(remove-if (lambda (edge) (some (lambda (v) (member v edge)) vs)) G))
(delete-vertices G '(0 3))DELETE-VERTICES
((1 2) (2 4) (1 1) (2 2) (4 4))Now, a function that returns the list of vertices of a graph
(defun vertices (G)
(if G (remove-duplicates (reduce #'union G))))
(vertices G)VERTICES
(3 1 0 2 4)Next, a function that returns the set of neighbors of a vertex in a graph:
(defun neighbors (G v)
(vertices (remove-if-not (lambda (edge) (member v edge)) G)))
(neighbors G 2)NEIGHBORS
(4 1 3 2)and a function that returns the subgraph induced by a collection of vertices:
(defun induced-subgraph (G vs)
(let* ((H (remove-if-not
(lambda (edge)
(every (lambda (x) (member x vs)) edge)) G))
(V (vertices H)))
(append H (loop for v in V collect (list v v)))))
(induced-subgraph G '(0 2 3))INDUCED-SUBGRAPH
((2 3) (0 0) (2 2) (3 3) (2 2) (0 0) (3 3))And finally an implementation:
(defun clique-number (G)
(if (null G)
0
(let* ((v (car (elt G (random (length G)))))
(H (delete-vertices G (list v))))
(max (clique-number H)
(1+ (clique-number (induced-subgraph H (neighbors G v))))))))CLIQUE-NUMBERand let us test on G we defined at the beginning:
(clique-number G)2First, let me write some functions that return a standard list of graphs: The discrete graph (vertices without any edges) on n vertices:
(defun discrete (n)
(loop for i from 0 below n
collect (list i i)))
(discrete 5)DISCRETE
((0 0) (1 1) (2 2) (3 3) (4 4))The star graph on n vertices:
(defun star (n)
(append (discrete n)
(loop for i from 0 below (1- n)
collect (list i (1- n)))))
(star 5)STAR
((0 0) (1 1) (2 2) (3 3) (4 4) (0 4) (1 4) (2 4) (3 4))The line graph on n vertices:
(defun line (n)
(append (discrete n)
(loop for i from 0 below (1- n)
collect (list i (1+ i)))))
(line 4)LINE
((0 0) (1 1) (2 2) (3 3) (0 1) (1 2) (2 3))The complete graph on n vertices:
(defun complete (n)
(loop for i from 0 below n
append (loop for j from i below n
collect (list i j))))
(complete 4)COMPLETE
((0 0) (0 1) (0 2) (0 3) (1 1) (1 2) (1 3) (2 2) (2 3) (3 3))The graph on n vertices on a cycle:
(defun cycle (n)
(append (line n) (list (list 0 (1- n)))))
(cycle 4)CYCLE
((0 0) (1 1) (2 2) (3 3) (0 1) (1 2) (2 3) (0 3))And the wheel graph on n vertices
(defun wheel (n)
(remove-duplicates (append (cycle (1- n))
(star n))
:test #'equal))
(wheel 4)WHEEL
((0 1) (1 2) (0 2) (0 0) (1 1) (2 2) (3 3) (0 3) (1 3) (2 3))So, here are some tests. First, discrete graphs:
(loop for i from 1 to 20 collect (clique-number (discrete i)))(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)Next, line graphs:
(loop for i from 2 to 20 collect (clique-number (line i)))(2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)Next, cycle graphs:
(loop for i from 3 to 20 collect (clique-number (cycle i)))(3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)Now, wheel graphs:
(loop for i from 4 to 20 collect (clique-number (wheel i)))(4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3)And finally complete graphs:
(loop for i from 3 to 20 collect (clique-number (complete i)))(3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)