Sachs algorithm

Sachs algorithm can be used on coronoid systems, but the deletion method of convex pair can not. An example is shown in Fig. 7. (u, v) is a convex pair in the coronoid system, but in any Kekule structure of the system, the edge uv is not a double bond edge. 

In Sect. 2, some relevant concepts and properties will be reviewed for preparation. The Sachs algorithm and the Sheng algorithm will be described with detailed proofs in Sect. 3 and 4, respectively. In Sect. 5, simple applications for special benzenoid systems will be reported. 

Figure 1 illustrates a simple application of the Sachs algorithm to determine the spectrum of the four-vertex butterfly graph. The adjacency matrix of the butterfly graph (Figure la) is the following 4x4 matrix ... 

The present paper is a review of the P-V path method. The concept of the P-V path was proposed by Gordon and Davison in 1952. In the last few years this method has been greatly developed and has become one of the important approaches for investigating Kekule structures of benzenoid hydrocarbons. The superiority of this method is its simplicity and visualization. According to the properties of the P-V path, some algorithmic approaches have been developed for deciding whether a benzenoid or a coronoid hydrocarbon is Kekulean. In 1985, John and Sachs introduced the concept of the P-V matrix and deduced the John-Sachs theorem which states that the absolute value of the determinant of the P-V matrix of a benzenoid or a coronoid hydrocarbon G is equal to the number of Kekule structures of G. 

Using the P-V path method, Sachs [8] obtained a number of topological properties for a benzenoid system. He proposed an algorithm, based on the topological properties, for recognizing the existence of Kekule structures. 

Based on the above two theorems Sachs proposed the following algorithm for recognizing Kekule structures ... 

The important problem of how to decide whether a given benzenoid system possesses Kekule structures or not has been investigated for a long time. The first fast algorithm was given by Sachs [5]. Recently necessary and sufficient structural requirements for the existence of Kekule structures in benzenoid systems have been discovered [6, 7], but these results do not provide a rapid method for recognizing Kekulean benzenoid systems. Also the P-V maximum flow method of He and He [8,9] should be mentioned. More recently the present author [10] put forward an algorithm which is much simpler and faster than that of Sachs. 

Sachs [5] put forward a simple algorithm for the existence of Kekule structures in the case of benzenoid systems where all peaks follow consecutively on the perimeter. Let B be such a benzenoid system. Along the perimeter, the peaks and valleys follow the order p2 p2 p - k - vfc 2 - . .. - v2. Here we assume that B has... 

Sachs C, Chaneac M, Rabouine P> Kindermans C, Dechaux M. Inadequate algorithm a cause for incorrect pH 7.4 correction in ionized calcium analyzers. Scand f Clin Lab Invest 1989 49 561-5. 

To find in peri-condensed benzenoid systems that do not represent a lattice is more involved. However, John and Sachs " " described an algorithm to obtain K values that can be linked to the GD algorithm and its generalization to lattices. The approach of John and Sachs is illustrated in Figure 36 for benzo[ Ai]-perylene, having two master and two slave rings, which are labeled by a,b and a, b respectively. Benzo[ Ai]perylene is not a lattice but can be viewed... 

Note that quite complex simulation algorithms are needed to estimate the maximum packing fraction of elHpsoids for details, see A. Donev, 1. Cisse, D. Sachs, E.A. Variano, F.H. StiUinger, R. Connelly, S. Torquato, P.M. Chaikin. Improving the density of jammed disordered packings using elHpsoids. Science, 303 (5660), 990-993,2004. 

---