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
What kind of issue would you like to report? (Optional)