Каноническая нумерация графов и библиотека nauty

Abstract

Canonical code is the notation for the graph structure, which is invariant to isomorphism. The article briefly illustrates the significance of canonical codes in general, and reveals some connection of the canonical code building to other problems common to computer science. A short overview of the currently popular algorithms is presented. The ideas of Brendan McKay's algorithm, implemented in his famous library «nauty», are described. That is, refinement of the vertex partition and use of automorphisms to prune the search tree. A simplified pseudo-code of the entire algorithm is shown.