Interface with Cliquer (cliquerelated problems)¶
This module defines functions based on Cliquer, an exact branchandbound algorithm developed by Patric R. J. Ostergard and written by Sampo Niskanen.
AUTHORS:
 Nathann Cohen (20090814): Initial version
 Jeroen Demeyer (20110506): Make cliquer interruptible (trac ticket #11252)
 Nico Van Cleemput (20130527): Handle the empty graph (trac ticket #14525)
REFERENCE:
Methods¶

sage.graphs.cliquer.
all_max_clique
(graph)¶ Returns the vertex sets of ALL the maximum complete subgraphs.
Returns the list of all maximum cliques, with each clique represented by a list of vertices. A clique is an induced complete subgraph, and a maximum clique is one of maximal order.
Note
Currently only implemented for undirected graphs. Use
to_undirected()
to convert a digraph to an undirected graph.ALGORITHM:
This function is based on Cliquer [NO2003].
EXAMPLES:
sage: graphs.ChvatalGraph().cliques_maximum() # indirect doctest [[0, 1], [0, 4], [0, 6], [0, 9], [1, 2], [1, 5], [1, 7], [2, 3], [2, 6], [2, 8], [3, 4], [3, 7], [3, 9], [4, 5], [4, 8], [5, 10], [5, 11], [6, 10], [6, 11], [7, 8], [7, 11], [8, 10], [9, 10], [9, 11]] sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.cliques_maximum() [[0, 1, 2], [0, 1, 3]] sage: C = graphs.PetersenGraph() sage: C.cliques_maximum() [[0, 1], [0, 4], [0, 5], [1, 2], [1, 6], [2, 3], [2, 7], [3, 4], [3, 8], [4, 9], [5, 7], [5, 8], [6, 8], [6, 9], [7, 9]] sage: C = Graph('DJ{') sage: C.cliques_maximum() [[1, 2, 3, 4]]

sage.graphs.cliquer.
clique_number
(graph)¶ Returns the size of the largest clique of the graph (clique number).
Note
Currently only implemented for undirected graphs. Use
to_undirected()
to convert a digraph to an undirected graph.EXAMPLES:
sage: C = Graph('DJ{') sage: C.clique_number() 4 sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]}) sage: G.show(figsize=[2,2]) sage: G.clique_number() 3

sage.graphs.cliquer.
max_clique
(graph)¶ Returns the vertex set of a maximum complete subgraph.
Note
Currently only implemented for undirected graphs. Use
to_undirected()
to convert a digraph to an undirected graph.EXAMPLES:
sage: C = graphs.PetersenGraph() sage: from sage.graphs.cliquer import max_clique sage: max_clique(C) [7, 9]