compute clique number of graph
find maximum clique in graph
(optional) equation of the form method = value; specify method to use
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.
G ≔ GraphComplement⁡CompleteGraph⁡3,4
G≔Graph 1: an undirected graph with 7 vertices and 9 edge(s)
In this case, the greedy algorithm also finds the optimum.
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.
Download Help Document