CanonicalGraph

CanonicalGraph[g]

gives a canonical form of the graph g.

CanonicalGraph[{vw,…}]

uses rules vw to specify the graph.

Details and Options

  • CanonicalGraph is also known as canonical graph labeling or canonical form of a graph.
  • CanonicalGraph is often used to compare and match a graph to a large collection of graphs.
  • CanonicalGraph[g] returns a graph with vertices 1, 2, … that is isomorphic to g.
  • Isomorphic graphs have the same canonical graph.
  • A Method option can be given. Possible Method settings include:
  • "Bliss"Bliss canonicalization
    "Nauty"Nauty canonicaliization

Examples

open allclose all

Basic Examples  (1)

Find a canonical graph of the Pappus graph:

These two graphs are isomorphic:

Scope  (4)

CanonicalGraph works with undirected graphs:

Directed graphs:

Use rules to specify the graph:

CanonicalGraph works with large graphs:

Applications  (1)

Find if two graphs are isomorphic:

The graphs are isomorphic if they have the same canonical graph:

Properties & Relations  (3)

A graph and its canonical graph are isomorphic:

Isomorphic graphs have the same canonical graph:

Use FindGraphIsomorphism to find a canonical ordering of vertices of a graph:

Wolfram Research (2014), CanonicalGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/CanonicalGraph.html (updated 2021).

Text

Wolfram Research (2014), CanonicalGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/CanonicalGraph.html (updated 2021).

CMS

Wolfram Language. 2014. "CanonicalGraph." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2021. https://reference.wolfram.com/language/ref/CanonicalGraph.html.

APA

Wolfram Language. (2014). CanonicalGraph. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/CanonicalGraph.html

BibTeX

@misc{reference.wolfram_2024_canonicalgraph, author="Wolfram Research", title="{CanonicalGraph}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/CanonicalGraph.html}", note=[Accessed: 21-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_canonicalgraph, organization={Wolfram Research}, title={CanonicalGraph}, year={2021}, url={https://reference.wolfram.com/language/ref/CanonicalGraph.html}, note=[Accessed: 21-December-2024 ]}