Theory Graph

Graph theory started with L. Euler and his paper in which he considers the problem of the seven bridges of Kdnigsberg (then East Pmssia, now Kaliningrad, Rnssia) [33]. Already in 1877, only 12 years after E. A. Kekule (1829-1896) originated his cyclic valence structnre of benzene, J. J. Sylvester (1814-1897), the first professor of mathematics at the Johns Hopkins University in Baltimore, recognized the potential 

FIGURE 2.11 Calculation of Kekule valence structures for selection of benzenoid hydrocarbons from the booklet of Clar on aromatic sextets. 

A graph is defined as a set of discrete elements (objects) Vj, referred to as vertices, and a binary relationship Rg, which indicates whether a pair of elements (vertices) are related or not. Pictorially, vertices are represented by small circles and 

Hydrogen suppressed molecular graph of adamantane defined by the list of vertices and the list of edges  

We shall extensively employ the notation of graph theory it provides a powerful and elegant formalism for the description of both the structure of the discrete lattices on which the CA live, and the complete dynamics (he. the global state transitions) induced by those structures. Graph theory also allows the correspondence between CA configurations and the words of a regular language to be made in a very natural fashion. 

Intuitively, a graph can be realized geometrically in a three-dimensional Euclidean space vertices arc represented by points and edges are represented either by lines (in the case of undirected graphs) or arrows (in the case of directed graphs). In this book, we will be concerned with both kinds of graphs multiple edges i.e. when vertices arc connected by more than one line or arrow), however, are not allowed. 

The order of a graph G is the number of vertices of G G = V G) = N. The size of G is the total number of edges in G 1 G 1 = E G) = M. In principle, the order and size of G may both be infinite, but we will mostly consider the case in which they are both finite. Clearly, for every M, 0 M ( ), there is a graph G N,M). The graph of order N and size ( ) is called a complete N-graph] it is 

A graph G N, M) is labeled if all of its N vertices are associated with N distinct labels in a one-to-one manner. An edge-labeled graph is defined in an analogous fashion. 

It is very important to understand what is meant by two graphs being the same or different . For this purpose we introduce the notion of graph isomorphism. Two graphs, G and G2, are isomorphic, which we write as Gi = G2, if there exists a bijection ij) V V2 which preserves adjacency (i.e. such that e i,j) 6 Ej if 

Many of the methods that will be covered in this chapter use a graph-theoretic representation of a molecule. These representations, which owe a great deal to chemistry as well as mathematics [3], are widely used by in sUico methods for drug discovery. Methods described in this chapter often use graph theory to describe molecules in a number of ways, reducing the most salient aspects for the application to which they are intended. 

Structure 14 G) f(G) Edge Density Diameter Radius Petitjean Shape Index Zagreb index 

The molecular representations and descriptors chscussed here provide a brief overview of the methods apphed in chemical information systems and their conventions. Many of the terms defined here will be of use in understanding the remainder of this chapter on using molecular topology (or graph) representations in identifying bioisosteres. 

At the time of Leonhard Ealer (the 18th century, Konigsberg had seven bridges across the Prcgcl river. Some of the townspeople wanted to know if there was a path through the town that allowed one to eross each of the seven bridges exactly once and finish at the starting point. 

the graph theory introduced by Euler in 1736 proved that it was not possible to walk through Konigsberg by crossing each bridge exactly once and ending up at the point where the path was started [36.  

---

From graph theory the main result needed in the present context is that the number of independent loops for a graph is given by ... 

S = number of streams including utilities (points in graph theory)... 

Wisemberg J and Kockarts G 1980 Negative ion chemistry in the terrestrial D region and signal flow graph theory J. Geophys. Res 85 4642-52... 

Another approach applies graph theory. The analogy between a structure diagram and a topological graph is the basis for the development of graph theoretical algorithms to process chemical structure information [33-35]. 

Figure 2-10. Different graph-theory representations of an identical diagram. In graph theory only the connections are important, not the length of the edges or the angles between them.

Figure 2-11. Phenylalanine can be represented in graph theory as a labeled, weighted graph with different atom and bond types (as on the left-hand side).

Graphs are used in mathematics to describe a variety of problems and situations [.37. The methods of graph theoi y analyze graphs and the problems modeled by them, The transfer of models and abstractions from other sciences (computer science, chemistry, physics, economics, sociology, etc.) to graph theory makes it possible to process them mathematically because of the easily understandable basics of graph theory. 

Table 2-4. Some basic definitions for graph theory. Graph theory term...

A connection table has been the predominant form of chemical structure representation in computer systems since the early 1980s and it is an alternative way of representing a molecular graph. Graph theory methods can equally well be applied to connection table representations of a molecule. 

Chemical Applications cf Graph Theory, A.T. Balaban (Ed.), Academic Press, London, 1976. 

Sci. 1989, 29(3), 227-228. p5] O. Ivanciuc, Coding the constitution -Graph Theory in chemistry, in Handbook of Chemoinfbrmatics, J. Gasteiger (Ed.), Wiley-VCH, Weinheim, 2003, Chapter II, Section 4. pq L. Euler, Soluho Problematis ad Geo-metriam Situs Pertinentis, Commen-tarii Academiae Sdentiarum Imperia-lis Petropolitanae 8,1736, pp. 128-140. p7] A. Beck, M. Bleicher, D. Crowe, Excursion into Mathematics, Worth, 1969. 

WC. Herndon, Canonical labelling and linear notation for chemical graphs, in Chemical AppUcations of Topology and Graph Theory, R.B. King (Ed.), Elsevier, Amsterdam, 1983, pp. 231-242. 

Mathematical theory of labeled colored graphs is exclusively used to formalize the structure and substructure search problem. There is almost a one-to-one correspondence between the terms used in graph theory and the ones used in chemical structure theory. Formally a graph G can be given by Eq. (1), where V is the set of graph vertices and H the set of edges. 

Because of the fundamental role of graph theory for the understanding of topological descriptors, some terms from graph theory are defined below. Then a selection of topological descriptors are discussed. 

In graph theory, the conversion of the adjacency matrix into the distance matrix is known as the "all pairs shortest path problem",... 

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1971. 

D. M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs, Theory and Applications, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995. 

Other techniques that work well on small computers are based on the molecules topology or indices from graph theory. These fields of mathematics classify and quantify systems of interconnected points, which correspond well to atoms and bonds between them. Indices can be defined to quantify whether the system is linear or has many cyclic groups or cross links. Properties can be empirically fitted to these indices. Topological and group theory indices are also combined with group additivity techniques or used as QSPR descriptors. 

Rubbery materials are usually lightly cross-linked. Their properties depend on the mean distance between cross links and chain rigidity. Cross linking can be quantified by the use of functions derived from graph theory, such as the Rao or molar Hartmann functions. These can be incorporated into both group additivity and QSPR equations. 

A review of graph theory teehniques for deseribing polymers is... 

The property calculation experiment offers a list of 34 molecular properties, including thermodynamic, electrostatic, graph theory, geometric properties, and Lipinski properties. These properties are useful for traditional QSAR activity prediction. Some are computed with MOPAC others are displayed in the browser without units. A table of computed properties can be exported to a Microsoft Excel spreadsheet. 

There are exceptions to this simple equation that occur infrequentiy but nevertheless must be considered. A more complete relationship for the number of exchangers, E, in a network is obtained by applying Euler s network relation from graph theory (6) ... 

Correlation methods discussed include basic mathematical and numerical techniques, and approaches based on reference substances, empirical equations, nomographs, group contributions, linear solvation energy relationships, molecular connectivity indexes, and graph theory. Chemical data correlation foundations in classical, molecular, and statistical thermodynamics are introduced. 

Molecular Connectivity Indexes and Graph Theory. Perhaps the chief obstacle to developing a general theory for quantification of physical properties is not so much in the understanding of the underlying physical laws, but rather the inabiUty to solve the requisite equations. The plethora of assumptions and simplifications in the statistical mechanics and group contribution sections of this article provide examples of this. Computational procedures are simplified when the number of parameters used to describe the saUent features of a problem is reduced. Because many properties of molecules correlate well with stmctures, parameters have been developed which grossly quantify molecular stmctural characteristics. These parameters, or coimectivity indexes, are usually based on the numbers and orientations of atoms and bonds in the molecule. 

R. J. Wilson, Introduction to Graph Theory, Academic Press, New York, 1972. 

To overcome the limitations of the database search methods, conformational search methods were developed [95,96,109]. There are many such methods, exploiting different protein representations, objective function tenns, and optimization or enumeration algorithms. The search algorithms include the minimum perturbation method [97], molecular dynamics simulations [92,110,111], genetic algorithms [112], Monte Carlo and simulated annealing [113,114], multiple copy simultaneous search [115-117], self-consistent field optimization [118], and an enumeration based on the graph theory [119]. 

A few topics have disappeared, and of course there are many gaps. One only has a finite number of pages and any text will naturally reflect the author s own experiences and preferences. Scattering theory and graph theory are both conspicuous by their absence, but there are several good texts on these subjects. 

---