GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/MaximumClique

GraphTheory

  

CliqueNumber

  

MaximumClique

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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

withGraphTheory:

GGraphComplementCompleteGraph3,4

GGraph 1: an undirected unweighted graph with 7 vertices and 9 edge(s)

(1)

DrawGraphG

CliqueNumberG

4

(2)

MaximumCliqueG

4,5,6,7

(3)

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

CliqueNumberG,method=greedy

4

(4)

MaximumCliqueG,method=greedy

4,5,6,7

(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.

• 

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

See Also

CliqueCover

GreedyClique

IndependenceNumber

IsClique

MaximumIndependentSet