FindClique - Maple Help

Online Help

All Products    Maple    MapleSim


GraphTheory

  

FindClique

  

find clique in graph

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

Calling Sequence

FindClique(G,size)

Parameters

G

-

graph

size

-

(optional) integer or range; size of clique to find

Description

• 

FindClique returns a list of vertices which comprise a clique in the graph G. The optional parameter size specifies a size for the clique. If size is omitted, FindClique behaves identically to MaximumClique and returns a maximum clique.

• 

The strategy is a branch-and-bound backtracking algorithm using the greedy color bound (see Kreher and Stinson, 1999).

• 

For a faster algorithm that usually, but not always, returns a large clique, see GreedyClique.

Examples

withGraphTheory:

GGraphComplementCompleteGraph3,4

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

(1)

DrawGraphG

FindCliqueG,3

2,1,3

(2)

FindCliqueG,4

4,5,6,7

(3)

References

  

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

Compatibility

• 

The GraphTheory[FindClique] command was introduced in Maple 2018.

• 

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

See Also

GreedyClique

IsClique

MaximumClique