Online Help

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.

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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{GraphComplement}\left(\mathrm{CompleteGraph}\left(3\,4\right)\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 7\; vertices\; and\; 9\; edges}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{CliqueNumber}\left(G\right)$

$4$

$\mathrm{MaximumClique}\left(G\right)$

$\left[4\,5\,6\,7\right]$

$\mathrm{CliqueNumber}\left(G\,'\mathrm{method}'='\mathrm{greedy}'\right)$

$4$

$\mathrm{MaximumClique}\left(G\,'\mathrm{method}'='\mathrm{greedy}'\right)$

$\left[4\,5\,6\,7\right]$

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

The GraphTheory[CliqueNumber] and GraphTheory[MaximumClique] commands were updated in Maple 2019.

The method option was introduced in Maple 2019.

For more information on Maple 2019 changes, see Updates in Maple 2019 .