Canonical Labelling

LA home
Computing
Algorithms
 glossary
 Graphs
  Directed
  DAG
  Undirected
  DF Trav
  Canonical
  Isomorphism
  Subg. Iso.
  Stable mrrg.
  Canonical
The graph canonical labelling problem is to find a function
canon : GVGV, s.t.
canon(G) is isomorphic to G, and
canon(Gγ) = canon(G),   ∀ γ ∈ Sn,
where the Vertex set V = {1, ..., n}, Sn is the group of all permutations over V, GV is the set of all graphs over V, and G ∈ GV.
Note, graphs G and G' are isomorphic iff canon(G) = canon(G').
 
One approach is to seek a labelling of G that gives the largest possible adjacency matrix, read as a binary number in some order, for example,
136 ...
248 ...
579 ...
... ... ... ...
If self-loops are not allowed, the diagonal can be ignored.
If the graph is undirected, only the right-upper (or left-lower) triangle need be considered.

(It may be convenient to make V = {0, ..., n-1} in programs.)

–adj.matrix

–output

Sources

Search for [canonical labelling maths graph] in the [bib].

www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Monday, 29-Nov-2021 22:47:52 EST.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.