N-tuple code

Lukovits (2000, 2002, 2004) and Lukovits and Gutman (2002) 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 (Aringhieri et al 1999). A graph is acyclic if it does not contain cycles. A tree is a connected acyclic graph. 

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 (Randic, 1986 Randid et al., 1988 Nikolic and Trinajstid, 1990 Trinajstid et al 1991), 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 (Randic, 1986). N-tuple codes also order isomeric 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 (von Knop et al., 1985 Trinajstid et al., 1991). 

In Figure 2.5, 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. 

Vector quantization. In vector quantization, not the individual filter bank output samples are quantized, but n-tuples of values. This technique is used in most current speech and video coding techniques. Recently, vector quantization has been applied in a scheme called TWIN-VQ ([Iwakami et al., 1995]). This system has been proposed for MPEG-4 audio coding (see [MPEG, 1997b]). 

Now that we have a code to canonize acyclic structures we can use an orderly algorithm. Next, we illustrate how the -tuple code enumerates alkanes up to n carbon atoms with a McKay-type orderly generation (Scheme III). For simplicity, all hydrogen atoms are ignored, and carbon atoms may thus have a number of bonds ranging between 1 and 4. As depicted in Figure 12, the initial graph contains one atom and no bond, so its canonical -tuple is (0). 

Figure 12 The three pentane isomers obtained with McKay s orderly algorithm and the -tuple code. Hydrogen atoms are not represented. All atoms are carbons and can have up to four bonds. Parent-child and child-parent relationships are indicated with arrows. Canonical w-tuples are written in parentheses. At each layer, a bond and a new atom are added. The added atom is represented by a solid node. The last bond/atom in the canonical -tuple is represented by a dashed line and is underlined in the canonical n-tuple. A graph is rejected when its legitimate parent is not the graph it came from. This case develops when the added bond/atom is not the last digit of the canonical -tuple (the dashed line is not linked to the solid node).

---