FindClique

FindClique[g]
finds a largest clique in the graph g.

FindClique[g,n]
finds a clique containing at most n vertices.

FindClique[g,{n}]
finds a clique containing exactly n vertices.

FindClique[g,{nmin,nmax}]
finds a clique containing between and vertices.

FindClique[g,nspec,s]
finds at most s cliques.

FindClique[{g,v},]
finds cliques that include the vertex v only.

DetailsDetails

  • A clique is a maximal set of vertices where the corresponding subgraph is a complete graph.
  • FindClique returns a list of cliques.
  • FindClique will return an empty list if there is no clique.
  • FindClique[,nspec,All] finds all the cliques.
  • For weighted graphs, FindClique gives a set of vertices with maximum sum of vertex weights.
  • FindClique works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

Background
Background

  • FindClique finds a set of cliques of specified size in a graph returned as a list of vertex lists. Here, a clique is a subset of vertices such that the corresponding induced subgraph is a complete graph. Cliques are used in project selection, pattern matching, finance, and network analysis. In general, FindClique[g,nspec,s] finds a set of s cliques of specified size nspec in a graph g.
  • FindClique[g] finds a single maximum clique (i.e. a clique of maximum possible size) and FindClique[g,{Length[FindClique[g][[1]]},All] finds all maximum cliques. (Note that some authors refer to maximum cliques simply as "cliques".) The size of the maximum clique is known as a graph's clique number, and the problem of finding the size of a maximum clique for a given graph is NP-complete.
  • Similarly, FindClique[g,Infinity] finds a single maximal clique, and FindClique[g,Infinity,All] finds all such cliques. Here, a maximal clique (note maximal and maximum cliques are not equivalent) is a clique that cannot be extended by including one more adjacent vertex, meaning it is not a subset of a larger clique. A maximum clique (i.e. clique of largest size in a given graph) is always maximal, but the converse does not hold. Maximal cliques are important in graph theoretic applications, including graph coloring and fractional graph coloring.
  • A maximal independent vertex set (which can be found using FindIndependentVertexSet) of a graph is equivalent to a maximal clique on its GraphComplement. FindKClique, FindKClan, and FindKClub find clique-like structures that allow less-than-complete connections in subgraphs.
Introduced in 2010
(8.0)
| Updated in 2014
(10.0)