|
- The graph canonical labelling problem is to find a function
- canon :
GV →
GV, 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,
-
1 | 3 | 6 | ... |
2 | 4 | 8 | ... |
5 | 7 | 9 | ... |
... | ... | ... | ... |
|
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.)
Sources
Search for [canonical labelling maths graph]
in the [bib].
|
|