 CanonicalGraph - Maple Help

GraphTheory

 CanonicalGraph
 construct graph with canonical labeling
 GraphNormal
 find the normal form of a graph Calling Sequence CanonicalGraph(G,opts) CanonicalGraph(M,opts) GraphNormal(G,opts) GraphNormal(M,opts) GraphNormal(M,ws,opts) Parameters

 G - a graph M - adjacency matrix for undirected unweighted graph ws - working storage opts - (optional) equation(s) of the form option = value where option is one of method, output, or storage Options

 • method=lexicographic or nauty
 This option controls which graph normalization algorithm is used. The default is nauty for CanonicalGraph and lexicographic for GraphNormal.
 • output=list or one of graph, labeling, or permutation
 The value can be the name graph, labeling, or permutation or a list of one or more of the names graph, labeling, and permutation. This option determines what is returned by CanonicalGraph. In all cases,
 The option output=labeling returns a list L which is a rearrangement of the vertex list of G corresponding to a canonical labeling.
 The option output=graph returns a graph whose edge set is identical to G, but whose vertex list is the rearrangement L.
 The option output=permutation returns a list representing the permutation which, if applied to Vertices(G), produces L.
 If output is a list of one or more of the symbols graph, labeling, or permutation, CanonicalGraph returns an expression sequence in which each element corresponds to what would be returned by invoking CanonicalGraph with the specified option in the order provided.
 • storage=rectangular, sparse, or auto
 This option controls whether the dense or sparse algorithm from the Nauty library is used. The values rectangular and sparse correspond to the dense and sparse algorithms, respectively, while the value auto automatically chooses which algorithm to employ based on a heuristic depending on the number of vertices and edges in G. The default is auto. Details

 • This command makes use of the Nauty library for computing automorphism groups and canonical labelings. Description

 • CanonicalGraph(G) constructs a representation of the graph G with a canonical labeling.
 • GraphNormal(G) is an alias for CanonicalGraph(G) which is behaves identically except the default value for the method option is lexicographic.
 • Owing to graph symmetries, it is possible that CanonicalGraph may return distinct vertex orderings when invoked on two graphs G and H with identical vertex sets and edge sets. The representation is nevertheless canonical in the sense that if G and H are isomorphic, AdjacencyMatrix(CanonicalGraph(G))=AdjacencyMatrix(CanonicalGraph(H)).
 • No general polynomial-time algorithm for computing a canonical labeling is presently known. Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

Find a canonical representation of a particular graph.

 > $\mathrm{G1}≔\mathrm{CartesianProduct}\left(\mathrm{CycleGraph}\left(3\right),\mathrm{CycleGraph}\left(4\right)\right)$
 ${\mathrm{G1}}{≔}{\mathrm{Graph 1: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (1)
 > $\mathrm{CG1}≔\mathrm{CanonicalGraph}\left(\mathrm{G1}\right)$
 ${\mathrm{CG1}}{≔}{\mathrm{Graph 2: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{CG1}\right)$ Display the computed canonical labeling for the specified graph.

 > $\mathrm{CanonicalGraph}\left(\mathrm{G1},\mathrm{output}=\mathrm{labeling}\right)$
 $\left[{"1:1"}{,}{"1:2"}{,}{"1:4"}{,}{"2:1"}{,}{"3:1"}{,}{"2:3"}{,}{"3:3"}{,}{"1:3"}{,}{"2:2"}{,}{"3:2"}{,}{"3:4"}{,}{"2:4"}\right]$ (3)

Observe that by permuting the vertices of the original graph, it is possible to generate a version of the graph for which CanonicalGraph returns a labeling distinct from the previous one.

 > $\mathrm{G2}≔\mathrm{PermuteVertices}\left(\mathrm{G1},\mathrm{Perm}\left(\left[12,10,8,6,4,2,11,9,7,5,3,1\right]\right)\right)$
 ${\mathrm{G2}}{≔}{\mathrm{Graph 3: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (4)
 > $\mathrm{CG2},L≔\mathrm{CanonicalGraph}\left(\mathrm{G2},\mathrm{output}=\left[\mathrm{graph},\mathrm{labeling}\right]\right)$
 ${\mathrm{CG2}}{,}{L}{≔}{\mathrm{Graph 4: an undirected graph with 12 vertices and 24 edge\left(s\right)}}{,}\left[{"3:4"}{,}{"3:3"}{,}{"3:1"}{,}{"2:4"}{,}{"1:4"}{,}{"2:2"}{,}{"1:2"}{,}{"3:2"}{,}{"2:3"}{,}{"1:3"}{,}{"1:1"}{,}{"2:1"}\right]$ (5)

Both labelings are canonical, as evidenced by the fact that the adjacency matrices of the resulting graphs are identical.

 > $\mathrm{EqualEntries}\left(\mathrm{AdjacencyMatrix}\left(\mathrm{CG1}\right),\mathrm{AdjacencyMatrix}\left(\mathrm{CG2}\right)\right)$
 ${\mathrm{true}}$ (6)

Find a canonical representation of a particular graph.

 > $\mathrm{G1}≔\mathrm{CartesianProduct}\left(\mathrm{CycleGraph}\left(3\right),\mathrm{CycleGraph}\left(4\right)\right)$
 ${\mathrm{G1}}{≔}{\mathrm{Graph 5: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (7)
 > $\mathrm{CG1}≔\mathrm{CanonicalGraph}\left(\mathrm{G1}\right)$
 ${\mathrm{CG1}}{≔}{\mathrm{Graph 6: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (8)
 > $\mathrm{DrawGraph}\left(\mathrm{CG1}\right)$ Display the computed canonical labeling for the specified graph.

 > $\mathrm{CanonicalGraph}\left(\mathrm{G1},\mathrm{output}=\mathrm{labeling}\right)$
 $\left[{"1:1"}{,}{"1:2"}{,}{"1:4"}{,}{"2:1"}{,}{"3:1"}{,}{"2:3"}{,}{"3:3"}{,}{"1:3"}{,}{"2:2"}{,}{"3:2"}{,}{"3:4"}{,}{"2:4"}\right]$ (9)

Observe that by permuting the vertices of the original graph, it is possible to generate a version of the graph for which CanonicalGraph returns a labeling distinct from the previous one.

 > $\mathrm{G2}≔\mathrm{PermuteVertices}\left(\mathrm{G1},\mathrm{Perm}\left(\left[12,10,8,6,4,2,11,9,7,5,3,1\right]\right)\right)$
 ${\mathrm{G2}}{≔}{\mathrm{Graph 7: an undirected graph with 12 vertices and 24 edge\left(s\right)}}$ (10)
 > $\mathrm{CG2},L≔\mathrm{CanonicalGraph}\left(\mathrm{G2},\mathrm{output}=\left[\mathrm{graph},\mathrm{labeling}\right]\right)$
 ${\mathrm{CG2}}{,}{L}{≔}{\mathrm{Graph 8: an undirected graph with 12 vertices and 24 edge\left(s\right)}}{,}\left[{"3:4"}{,}{"3:3"}{,}{"3:1"}{,}{"2:4"}{,}{"1:4"}{,}{"2:2"}{,}{"1:2"}{,}{"3:2"}{,}{"2:3"}{,}{"1:3"}{,}{"1:1"}{,}{"2:1"}\right]$ (11)

Both labelings are canonical, as evidenced by the fact that the adjacency matrices of the resulting graphs are identical.

 > $\mathrm{EqualEntries}\left(\mathrm{AdjacencyMatrix}\left(\mathrm{CG1}\right),\mathrm{AdjacencyMatrix}\left(\mathrm{CG2}\right)\right)$
 ${\mathrm{true}}$ (12) Compatibility

 • The GraphTheory[CanonicalGraph] command was introduced in Maple 2017.