As yesterday, assume we have a simple graph \(G=(V,E)\). A clique is a collection of vertices \(U\subseteq V\) such that every pair of elements \(u\neq v\) form an edge, i.e. \(\{u,v\}\in E\). Notice that \(U\) is a clique if \(U\) is an independent set in the complement graph \(G^c=(V,E^c)\). 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 \(\omega(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.
\[ \omega(G) = \max( \omega(G-v), 1 + \omega( Ind_G(N(v))-v ) ) \] where
\(G-v\) is the graph obtained from \(G\) by removing \(v\) and all edges incident to \(v\)
\(Ind_G(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)