The All-Path Matrix

The all-path matrix, denoted by P, is a square symmetric V x V matrix whose i-j entry is the sum of the lengths of all paths p(i, j) connecting vertices i and j (Todeschini and Consonni, 2000, 2009)  

From the above definition, it follows that for simple acyclic graphs the all-path matrix is identical to the vertex-distance matrix. For acyclic graphs, the total path-connt P is given by a simple expression  

The all-path matrix is used for the computation of the all-path Wiener index (Lukovits, 1998). 

---

The all-path Wiener index can be calculated more easily on the all-path matrix which is a square synunetric AxA matrix, A being the number of graph vertices, whose i-j entry is the sum of the lengths of all the paths p,y coimecting vertices v,- and... 

The all-path Wiener index is derived from the all-path matrix as ... 

The all-path matrix of Gj (see structure A in Figure 2.1) is exemplified below ... 

The detour-path matrix Ap, analogously defined as the -> distance-path matrix Dp is a square symmetric matrix Ax A whose off-diagonal entry i-j is the count of all paths of any length m ( < m < A,) that are included within the longest path from vertex v, to vertex vy (A,y) [Diudea, 1996a]. The diagonal entries are zero. 

A layer matrix obtained weighting all atoms by the - path degree Therefore, the entry i-k of the matrix is the sum of the path degrees of all atoms located at distance k from the focused / th vertex. The half-sum of the elements in the first column k = 0) is equal to the half-sum of the elements in each row of LPD matrix and corresponds to a molecular descriptor recently reproposed as the -> all-path Wiener index i.e. the following relations hold ... 

It has to be noted that the all-path Wiener index coincides with a previously proposed global index obtained as the half-sum of any row of the path degree layer matrix LPD. 

The detour-path matrix, denoted by DM, can similarly be defined as the vertex-distance-path matrix that is, the matrix DM is a square symmetric L x L matrix whose off-diagonal elements i,j count all paths of any length that are included within the longest path between vertex i and vertex j (Diudea, 1996a). Each element i,j of the DM is computed from the corresponding detour matrix as follows ... 

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

There are no rows with all zero elements in the reduced matrix of Fig. 9a, hence we proceed to the second phase of Steward s algorithm by starting with the first row of the reduced matrix to trace the path 2 - 3 -> 4 -> 2. The loop of information flow between vertices 2, 3, and 4 is encircled by the dashed line in the graph in Fig. 9b. The rows and columns labeled 2, 5, and 4 are next removed from the reduced matrix and one row, which is the Boolean union of the rows labeled 2, 3, and 4, and one column, which is the Boolean union of the columns labeled 2, 2, and 4, are added to the reduced matrix to obtain the new reduced matrix of Fig. 10a. The added row and column are labeled... 

Fig. 6. All paths leading from the initial to the final points in time t contribute an interfering amplitude to the path sum describing the resultant probability amplitude for the quantum propagation. In this double slit free particle case, two paths of constant speed are local functional stationary points of the action, and these two dominant paths provide the basis for a (semiclassical) classification of subsets of paths which contribute to the path integral. In the statistical thermodynamic path expression, the path sum is equal to the off-diagonal electronic thermal density matrix...

The distance matrix D(G) of a graph G is another important graph-invariant. Its entries dy, called distances, are equal to the number of edges connecting the vertices i and j on the shortest path between them. Thus, all dy are integers, including du = 1 for nearest neighbours, and, by definition, d = 0. The distance matrix can be derived readily from the adjacency matrix ... 

---