The Adjacency Matrix

Given a graph G with n vertices, the adjacency matrix A is a square nxn symmetric matrix (Eq. 9 ). 

---

The adjacency matrix of a molecule con.si.sting of n atom.s i.s a square (n / n) matrix. with the entric.s giving all the connectivities of the atoms. The intersection of a row and a column obtains a value of 1 if the corresponding atoms are connected. If there is no bond between the atoms being considered, the position in the matrix obtains the value 0. Thus, this matrix representation is a Boolean matrix with bits (0 or I) (Figure 2-13). 

With such a matrix representation, the storage space is dependent only on the number of nodc.s (atoms) and independent of the number of bonds. As Figure 2-14 dcmon.stratcs, all the e.sscntial information in an adjacency matrix can also be lound in the much smaller non-rediindant matrix. But the adjacency matrix is unsuitable for reconstructing the constitution of a molecule, because it does not provide any information about the bond orders. 

The bond matrix is related to the adjacency matrix but gives information also on the bond order of the connected atoms. Elements of the matrix obtain the value of 2 if there is a double bond between the atoms, c.g, between atoms 2 and 3... 

Then the Lapladan matrix I of a simple graph G can be calculated from the diagonal matrix DEG and the adjacency matrix A following Eq. (11). 

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

EXAMPLE Cousklo.r a oiie-dimeiisioiial lattice of si/.e N = 5. The adjacency matrix, L, and Smith Canonical Form of L — xl, are, respectively,... 

Table 6.2 Number of nodes Ht, C = 0,.. . 4 in the minimal deterministic state transition graph (DSTG) representing the regular language r2t[0, where 0 is an elementary fc = 2, r = 1 CA rule Amax is the maximal eigenvalue of the adjacency matrix for the minimal DSTG and determines the entropy of the limit set in the infinite time limit (see text), Values are taken from Table 1 in [wolf84a. ...

The second measure can be obtained directly from the adjacency matrix A= [aij] of G. Recalling that aij = 1 if vertices i and j are adjacent and 0 otherwise, it is not hard to show (essentially by using induction on the power k), that [a j]... 

The adjacency matrix A(G) of a molecular graph G with N vertices is the square NxN symmetric matrix in which [A],j=l if vertex Vj is adjacent to vertex Vj and [A],j=0 otherwise. The adjacency matrix is symmetric, with all elements on the main diagonal equal to zero. The sum of entries over row i or column i in A(G) is the degree of vertex Vj, 5j. Usually, the adjacency matrix is based on weighted molecular graphs in which heteroatoms are represented as vertex parameters and... 

A (finite) directed graph or digraph consists of a finite set of vertices and a set of ordered pairs of vertices called arcs. We denote by VG and Eg the set of vertices and arcs of the digraph G, respectively. Given an ordering of the vertices, the adjacency matrix of a digraph G on n vertices, denoted by AG, is the (0, l)-matrix where the ij-th element... 

Figure 4 A 3-regular graph of size 4 together with a possible edge-colouring the edge-colouring matrices correspond to entries having the same colour in the adjacency matrix A of the graph.

The adjacency matrix ALG of the line-graph of G can then be written in the form (Severini 2003, Severini and Tanner 2004)... 

The eigenvalues of the adjacency matrix are obtained from the following determi-nantal equation ... 

Note the general similarities between Eqs. (4) and (5). In equation (5) the energy matrix H and the overlap matrix S can be resolved into the identity matrix I and the adjacency matrix A as follows ... 

The energy levels of the Hiickel molecular orbitals [Eq. (5)] are thus related to the eigenvalues xk of the adjacency matrix A (equation 4) by the following equation ... 

Correspond to the Maximal Loops in the Adjacency Matrix and are Invariant of the Output Set. 200... 

Figure 1 illustrates a digraph. The rows of the adjacency matrix correspond to the vertices to which flow is directed. The columns correspond to the vertices from which the flows are directed. 

The edge of the graph from vertex / to vertex 2 indicates a flow of information or perhaps material from vertex 1 to 2 and therefore the element r2l = 1. Similarly, there is a flow directed from vertex 1 to vertex 3 so that r31 = 1 also r43 = 1 and r14 = 1. All other elements of the matrix are 0 since there are no other flows in the graph. The adjacency matrix thus indicates all of the one step paths (flows between two vertices without an intervening vertex) between vertices. If ri = 1, there is a one-step path from vertex./ to vertex Therefore, all of the structure of the graph is contained in the adjacency matrix. 

An important property of the adjacency matrix is that the ith power of this matrix gives all the i step paths between vertices. For example, the second and third powers of the adjacency matrix in Fig. 1 are shown in Fig. 2. The... 

One method of locating these maximal loops is to compute the reachability matrix, R (H1), which is the element by element Boolean union of all of the powers of the adjacency matrix up to the nth, where n is the number of rows of R. An element of the reachability matrix is defined as... 

To form the adjacency matrix in a simpler way, note that the elements of the first column of the adjacency matrix in Fig. 7b correspond exactly to the elements of the first column of the occurrence matrix in Fig. 6 if the output element is deleted. Similarly, the elements of column 2 of the adjacency matrix correspond exactly to the elements of the fourth column of the occurrence matrix if the output element is deleted. Therefore, if the columns of the occurrence were permuted until all of the output elements appeared on the main diagonal, as in Fig. 7a, the nonzero elements of the occurrence matrix... 

One method of partitioning the system equations is to compute the maximal loops using powers of the adjacency matrix as discussed in Section II. Certain modifications to the methods of Section II are needed in order to reduce the computation time. The first modification is to obtain the product of the matrices using Boolean unions of rows instead of the multiplication technique previously demonstrated to obtain a power of an adjacency matrix. To show how the Boolean union of rows can replace the standard matrix multiplication, consider the definition of Boolean matrix multiplication, Eq. (2), which can be expanded to... 

In order to obtain in a digital computer all of the powers of the adjacency matrix and then compute the reachability matrix by taking the Boolean sum of all of the powers, each power of the adjacency matrix and the reachability matrix would have to be stored in the computer memory. For large systems of equations an unreasonable amount of storage would be required. A second modification to the methods described in Section II is to drastically reduce... 

---