dwave.graphs.algorithms.clique.clique_number#
- clique_number(G, sampler, lagrange=2.0, **sampler_args)[source]#
Returns the number of vertices in the maximum clique of a graph.
A maximum clique is a clique of the largest possible size in a given graph. The clique number math: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.
This function works by finding the maximum independent set of the compliment graph of the given graph G which is equivalent to finding maximum clique. It defines a QUBO with ground states corresponding to a maximum weighted independent set and uses the sampler to sample from it.
- Parameters:
G (NetworkX graph) – The graph on which to find a maximum clique.
sampler (
dimod.Sampler) – A dimod sampler.lagrange (optional (default 2)) – Lagrange parameter to weight constraints (no edges within set) versus objective (largest set possible).
sampler_args – Additional keyword parameters are passed to the sampler.
- Returns:
clique_nodes – List of nodes that form a maximum clique, as determined by the given sampler.
- Return type:
Notes
Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.
References