T1Lukovits [33-36] offered an approach by which the vertex-adjacency matrix of an acyclic structure can be replaced by a single number, called the compressed (vertex-)adjacency matrix code, denoted by CAM. Here we present besides the CAM code, the N-tuple code of trees that induces the unique labeling of trees [371].
The N-tuple code has initially been derived for trees [89-93]. It consists of a string of non-negative integers, each representing the degree of a vertex in a tree or subtree. The degree of a vertex in a (molecular) graph is equal to the number of edges meeting at this vertex. To generate the N-tuple code, one has first to identify the vertices of the highest degree and select amongst them one that will result in a code that produces lexicographically the largest number. After the initial vertex is located, that vertex and the edges adjacent to it are removed and the subtrees thus produced are examined. This means searching for the largest chain, and, if several chains of the same length appear, their codes are derived and combined in such a way that the resulting N-tuple code corresponds to the lexicographically highest number. The steps which can speed up the search of the N-tuple code can be summarized as follows:
(1) locate vertices of the highest degree;
(2) locate the longest path;
(3) backtrack to the last branching point to visit all vertices in the branch;
(4) continue the process till all vertices branching from the longest path have been accounted for then
(5) locate the next longest path and continue the process until all vertices have been recorded.
It is important to point out that two non-isomorphic trees cannot have the same N-tuple.
The N-tuple codes are brief-their length is given by V, the number of vertices in a tree. Therefore, they belong to the linear compact codes [94-96], so named because they use a limited number of digits for linearly encoding a given molecular structure .
Another important property of the N-tuple code is that it induces a unique labeling of vertices in an acyclic graph [94]. N-tuple code also order isometric acyclic graphs in accordance with their mode of branching. Additionally, the N-tuple approach has been used to develop a very powerful computer program for generation and enumeration of various kinds of (chemical) trees [91,93].
In Figure 6, we give as an illustrative example a branched tree representing the carbon skeleton of 2,2,3-trimethylhexane and the labels of its vertices produced by the N-tuple code. The N-tuple code of 2,2,3-trimethylhexane is 421100000.
Figure 6. A branched tree representing the carbon skeleton of 2,2,3-trimethylhexane and the vertex-labels induced by N-tuple code.
The vertex-adjacency matrix of T1 is as follows:
vA(T1)= |
 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|||
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|||
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|||
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
The structure of the vertex-adjacency matrix is such that it contains only one non-zero element in each column of its upper (or in each row of its lower) triangle. This fact allows one to replace the vertex-adjacency matrix by the CAM code. Each digit in the CAM code denotes the row in the upper-half of the vertex-adjacency matrix in which the digit 1 is placed. Thus the CAM code is a linear representation of the vertex-adjacency matrix composed of V-1 entries. Different tree labeling lead to a different CAM. The resulting CAM code of T1 is 12342111. It should be also noted that the CAM code can be determined directly by inspecting the labeling of a tree.
The vertex-adjacency matrix and the corresponding tree can be easily recovered from the CAM code. Let us consider the following CAM code: 12335567. This code represents the compact form of the following matrix:
| vA= | |
0 | 1 |
|
|||||||
0 |
1 |
||||||||||
0 |
1 |
1 |
|||||||||
0 |
|||||||||||
0 |
1 | 1 | |||||||||
| 0 | 1 | ||||||||||
| 0 | 1 | ||||||||||
| 0 | |||||||||||
0 |
The corresponding tree is presented in Figure 7.
Figure 7. A branched tree representing the carbon skeleton of 3-ethyl-4-methylhexane and the vertex-labels induced by the CAM code.
This particular type of the CAM code has been introduced by Lukovits [33] who called it the lowest degree first (LDF) code.
