ABSTRACT
Among the most important concepts common to all areas of mathematics are isomorphism and symmetry. The detection of isomorphic structures is essential in the construction of practical algorithms. This chapter presents a polynomial time algorithm to determine isomorphism of trees. It gives a general graph isomorphism algorithm that uses the method of invariants or repeated refinement. Isomorphism of combinatorial structures is studied in this chapter. Once all of the induced invariants are evaluated for the two graphs and the final partitions of the vertices are reached, a backtracking algorithm can be used to determine which of the correspondences are actual isomorphisms. The technique of using invariants is among the earliest methods used for determining isomorphism. The method of using balanced binary strings of length 2n as a certificate for trees on n vertices is due to Ronald Read.
