Skip to main content
`Ctrl`+`K`

# max_clique

max_clique(G)

  Find the Maximum Clique

  Finds the \(O(|V|/(log|V|)^2)\) apx of maximum clique/independent set in the worst case.

  Parameters:
    G NetworkX graph

      Undirected graph

  Returns:
    clique set

      The apx-maximum clique of the graph

  Raises:
    NetworkXNotImplemented

      If the graph is directed or is a multigraph.

  Notes

  A clique in an undirected graph G = (V, E) is a subset of the vertex set `C subseteq V` such that for every two vertices in C there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph).

  A maximum clique is a clique of the largest possible size in a given graph. The clique number `omega(G)` of a graph G is the number of vertices in a maximum clique in G. The intersection number of G is the smallest number of cliques that together cover all edges of G.

  https://en.wikipedia.org/wiki/Maximum_clique

  References

  [1]

  Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer. doi:10.1007/BF01994876

  Examples

      >>> G = nx.path_graph(10)
      >>> nx.approximation.max_clique(G)
      {8, 9}