Graph automorphism

Remark (A test on chirality) Orientation functions obtained from each other by a graph-automorphic renumbering are isomorphic. A conformation is achiral if and only if its orientation function is isomorphic to its negative. 

S should be closed under permutations of the quadruples and under application of graph automorphisms of the molecule. In other words, if (ao,ai, 2. 3)eS, then each permutation (oj, Uj, a ), with i, j, k,l =4 of this quadruple should be contained in S, and for each graph automorphism n, the quadruple (ff(flo). rr(fli). rrfo ). n(aj)) should also be in S. 

This way, applying a graph automorphisms to a POP with respect to Swill result in a POP with respect to the same selection S. We can introduce canonic forms for POPs with respect to Sand generate canonic representatives only, avoiding the generation of isomorphic conformations. 

POFs Xo nd Xi correspond to the two enantiomers shown in Figure 4.3. POF X2 is not chemically realizable. However, it is geometrically realizable Any planar placement of the five atoms has the POF X2-b There are 3 = 729 abstract POFs for structure 4.2b, cyclohexane. Each of the 6 selected increasing quadruples can have the orientation plus, minus, or zero independently. However, cyclohexane has 12 graph automorphisms. Considering relabelings according to these permutations, some of the abstract POFs are isomor-... 

Similarly, POF describes conformer 8 , which is the mirror image of 8. Since 8 is achiral, mirror image 8 is identical with original 8, except for the numbering. Again, numbering of 8 is obtained from that of 8 by appUcation of the graph automorphism. 

See, for example, M. Razinger, K. Balasubramanian, and M. E. Munk,/. Chem. Inf. Comput. Sci., 33, 197 (1993). Graph Automorphism Perception Algorithms in Computer-Enhanced Structure Elucidation. C. Jochum and J. Gasteiger, J. Chem. Inf. Comput. Sci., 17, 113 (1977). Canonical Numbering and Constitutional Symmetry. See also Ref. 7... 

The problem of canonical coding, graph isomorphism, and graph automorphism has both mathematical and chemical significance. The mathematical formulation of the problem is briefly set out below, and some cormections with the chemical counterpart are presented. In the subsequent sections, the main algorithms used in chemistry for canonical coding of molecular graphs and constitutional symmetry perception are presented and compared. 

---