general.hpp File Reference

Plans regarding graph isomorphisms. More...

Go to the source code of this file.

Detailed Description

Plans regarding graph isomorphisms.

Create milestones
Connections to other modules
Overview on implementations
  • Maxima
    1. isomorphism(g1,g2)
    2. is_isomorphic(g1,g2)
    are the two available functions from the graphs-package, using a very simple backtracking algorithm. Regarding groups, apparently only todd_coxeter is available, which computes the order of a group presentation through relations.
  • Sage
    1. N.I.C.E. implements nauty, which apparently computes the lexicographical canonical numbering (?; see below), and also generators for the automorphism group (of one or of both graphs?).
    2. The current documentation (2.7.2) doesn't say much, and one needs to read the literature.
    3. There is also substantial support for combinatorial group theory.
  • Boost
    1. See Graphs/Isomorphisms/SimpleBacktracking.cpp for an application.
  • Gap
The lexicographical canonical numbering
  • For {0,1}-vectors of the same length we have the linear order given by the lexicographical order (with the 0-vector as smallest and 1-vector as largest element).
  • An ordered graph yields an ordered adjacency matrix; the rows of this matrix can be concatenated, yielding a {0,1}-vector, for which then the lexicographical order applies.
  • So on ordered graphs with the same number of vertices we have a linear order.
  • Now for a graph one considers some vertex order which yields the smallest associated ordered graph.
  • The associated {0,1}-vector is a complete invariant for graph isomorphism, and choosing some associated vertex order (by some rule) yields a canonical numbering (two graphs are isomorphic iff the canonical numbering yields an isomorphism).
  • This all follows from the fact that two graphs are isomorphic iff their adjacency matrices are isomorphic (as combinatorial square matrices), where combinatorial square matrices are isomorphic iff they can be ordered to be equal.
  • Does this canonical numbering establish a functor?
  • For combinatorial square matrices over linearly ordered sets we can consider a canonical ordering, which yields the lexicographically smallest ordered representation.
  • The first approach is to find such canonical numberings and their the associated invariants by brute force.
  • Is the problem of finding such a canonical numbering in NP?
  • Obviously instead of graphs we can allow multigraphs with loops (i.e., symmetric matrices over NN_0), and also multi digraphs with loops (i.e., square matrices over NN_0).
  • Since two general graphs are isomorphic iff the underlying multigraphs with loops are isomorphic, also general graphs can be handled here. (Note though that general graphs allow for more morphisms, since the edges have an identity.)

Definition in file general.hpp.