Clique

Sometimes we are interested in finding the largest subset of the vertices such that for every pair of vertices $P_i$ and $P_j$ in the subset, both $P_i \rightarrow P_j$ and $P_j \rightarrow P_i$ hold.

We define a clique as follow:

A subset of a directed graph satisfying the following conditions is called a clique:
i) The subset contains at least 3 points.
ii) If $P_i$ and $P_j$ are in the clique, then $P_i \leftrightarrow P_j$ holds.
iii) The subset is the largest possible.

Example:

In the following graph we have two cliques $C_1$ and $C_2$ .

Figure 16

$C_1$ = { $P_1, P_2, P_3, P_4$}

$C_2$ = {$P_5, P_6, P_7$}
$P_1, P_2, P_3$} is not a clique because it is not largest subset; we can add $P_4$ to it and still have (i) and (ii) satisfied.

Now you might ask if there is a large and complicated graph, how easy it is to find a clique in the graph?

Let S be an n x n matrix defined as

$S_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{if } P_i \leftrightarrow P_j\\ 0 & \mbox{otherwise}\\ \end{array} \right.$
It can be shown that if ${S_{ii}}^{(3)} \neq 0$, then $P_i$ belong to a clique.

Example:

Find all cliques of the following graph .

Figure 14

First find the matrix $S$.

$S = \left[ \begin{array}{rrrrrrrrr} 0&1&0&1&0&0&0&0&0\\ 1&0&1&1&0&0&0&0&0\\... ...&0&1&0&0&0\\ 0&0&0&0&1&0&0&0&1\\ 0&0&0&0&0&0&0&1&0\\ \end{array} \right]$

compute $S^3$ = $\left[ \begin{array}{rrrrrrrrr} 2&5&2&5&0&0&0&0&0\\ 5&4&5&5&0&0&0&0&0\\ ... ...&0&2&0&1&0\\ 0&0&0&0&3&0&1&0&2\\ 0&0&0&0&0&1&0&2&0\\ \end{array} \right]$

So $C_1$ = { $P_1, P_2, P_3, P_4\}$ is a clique and $C_2 = \{P_5, P_6, P_7 \}$ is an other clique. But $P_8$ and $P_9$ do not belong to any clique.