Graph-theoretical elements

1 Definition (Walk, path, cycle, ring, tree) Consider an m-multigraph on n nodes y th cot responding bond graph y and a natural number k 0. A sequence (fo. T) of nodes in y gives rise to the following definitions  

The sequence is called a wa//c starting from node iq and ending in iT if the pairs of nodes f, ), 

An open walk is a path if its nodes are pairwise different. A closed walk (ig,. i = ig) is a cycle if there are no repetitions of nodes or bonds except for = I o, and if the only bonds between any two nodes v and h in graph y are bonds between neighbors in the closed walk. In formal terms, 

Later on we shall introduce descriptors of molecules that are applied in Chapter 7. One of them is the number mwc (y), the number of walks of given length Z in y. In the following example we should like to remind the reader that we walk along bonds, not along lines, and that we can use the same bond repeatedly. 

It is obvious that we might also consider the corresponding expressions in terms of the multiplicities, see [269]. The resulting counts of multiwalks better reflect 

---

To use the wavefunction P of (5.1.1) one needs to evaluate its matrix elements. One way to do this is to compute representation matrices on the basis of Kekule structures, then sum the elements of these matrices. But graph-theoretic representations for the overall matrix element of may also be obtained. Using (4.2.4) with the sign convention possible for alternants, one obtains... 

Second, even if the number of knowns in Eq. (5) were greater than or equal to the number of unknowns, a new type of uncertainty would be observed. As stated previously, we set the values of the S vector to (0,1), i.e., the parameters derived from the spectrum are crisp. From the values of these parameters assigned to the vertices, the structure of the unknown molecule (given by the elements a of the adjacency matrbc) is to be deduced. From a graph-theoretical point of view these vertices may be considered as colored by different spectral parameters, e.g., chemical shifts from NMR spectra, or by frequencies in IR spectroscopy, etc. This can be done by assignment of these parameters to the corresponding atoms. The assignment procedure implies that the experimental values are compared with values assumed or evaluated from the structure. Insofar as these parameters are functions of the atom connectivity environment, they are widely used to elucidate structural connectivity. Several severe problems... 

LCR uses a graph theoretic representation of molecular structures, wherein nodes are atoms and edges are bonds. Three modeling elements are employed to create and describe chemical structures. Each modeling element has been implemented as a class, in an object-oriented programming environment, and is described by a set of attributes and a set of procedures. 

M is a graph-theoretical matrix, n the matrix dimension, c Ch(M x))j the ith coefficient of the characteristic polynomial of M, A(M) indicates the graph spectrum (i.e., the set of eigenvalues of M), and a and X are real parameters. In function VSj(M) is the ith matrix row sum, Kthe total number of selected graph fragments, and the number of vertices in the fcth fragment. o,j indicates the elements of the adjacency matrix that are equal to 1 for pairs of adjacent vertices and zero otherwise. 

A general approach to derive a local vertex invariant from a symmetric graph-theoretical matrix (A x A) is to compute the sum of the elements in the ith rosv, or jth column, of the matrix M ... 

Given tv ro equal-sized graph-theoretical matrices Mi and M2, sum matrices, denoted as are obtained by summing corresponding elements of matrices Mi and M2 ... 

Given two graph-theoretical matrices Mj and M2 of the same size, quotient matrices are matrices, denoted by M1/M2, whose elements are given by the ratio of the off-diagonal elements... 

Given two graph-theoretical matrices Mi and M2 of the same size, combined matrices, denoted by Mi AM2, are unsymmetrical matrices whose upper matrix elements are the elements of Ml and lower matrix elements are those of M2 ... 

Combinatorial matrices, denoted by Mb, are defined in terms of the binomial coefficient of the elements of a graph-theoretical matrix M. Each entry U-j of the combinatorial matrix is calculated as the following [Diudea, 1996a] ... 

For any square symmetric graph-theoretical matrix M, whose diagonal elements are equal to zero, the Wiener-type indices, denoted by Wi, are defined as half sum of the entries of the matrix ... 

It is well known that substructure search is not so much a chemical but rather a graph theoretical problem. Compared to common numerical problems, graph theoretical problems show an unpleasant behaviour. Consider for example a finite element problem. Here the number of operations to solve the problem is linearly proportional to... 

---