CliqueNumber - Maple Help

GraphTheory

 CliqueNumber
 compute clique number of graph
 MaximumClique
 find maximum clique in graph

 Calling Sequence CliqueNumber(G) CliqueNumber(G, opt) MaximumClique(G) MaximumClique(G, opt)

Parameters

 G - graph opt - (optional) equation of the form method = value; specify method to use

Options

 • method=one of exact, greedy, sat, or hybrid.
 Specifies the algorithm to use when computing the maximum clique. The exact method uses a branch-and-bound backtracking algorithm using the greedy color bound (see Kreher and Stinson, 1999). The sat method finds a maximum clique by first encoding the problem as a logical formula and the hybrid method (used by default) runs the exact and sat methods in parallel and returns the result of whichever finishes first. The greedy method uses a heuristic which is fast but not guaranteed to return a maximal clique.

Description

 • CliqueNumber returns the number of vertices in a largest clique of the graph G. This is equal to the independence number of the graph complement of G.
 • MaximumClique returns a list of vertices which comprise a largest clique.
 • The problem of finding a maximum clique for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known. The exhaustive search will take an exponential time on some graphs. For a faster algorithm that usually, but not always, returns a relatively large clique see GreedyClique. This algorithm can also be selected by using the method = greedy option.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{GraphComplement}\left(\mathrm{CompleteGraph}\left(3,4\right)\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 7 vertices and 9 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{CliqueNumber}\left(G\right)$
 ${4}$ (2)
 > $\mathrm{MaximumClique}\left(G\right)$
 $\left[{4}{,}{5}{,}{6}{,}{7}\right]$ (3)

In this case, the greedy algorithm also finds the optimum.

 > $\mathrm{CliqueNumber}\left(G,'\mathrm{method}'='\mathrm{greedy}'\right)$
 ${4}$ (4)
 > $\mathrm{MaximumClique}\left(G,'\mathrm{method}'='\mathrm{greedy}'\right)$
 $\left[{4}{,}{5}{,}{6}{,}{7}\right]$ (5)

References

 D.L. Kreher and D.R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search", CRC Press, Boca Raton, Florida, 1998. doi:10.1145/309739.309744

Compatibility

 • The GraphTheory[CliqueNumber] and GraphTheory[MaximumClique] commands were updated in Maple 2019.
 • The method option was introduced in Maple 2019.