5.14 The All-Path Matrix

The all-path matrix, denoted by AP, 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 [21]:

[AP]ij=
  ∑|p(i,j)|            if i ≠ j
  0                     otherwise                                       (112)      

where |p(i,j)| denotes the length of a path between vertices i and j. The all-path matrix is a graph-theoretical representation of molecules based on the total path-count.

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-count P is given by a simple expression:

P = (V2-V)/2                                (113)      

The total path-count for graphs containing cycles requires specific counting algorithms.

The all-path matrix for the graph G1 (see structure A in Figure 2) is exemplified below.

AP(G1)=
0
1
2
8
8
8
10
1
0
1
6
6
6
8
2
1
0
4
4
4
6
8
6
4
0
4
4
6
8
6
4
4
0
4
6
8
6
4
4
4
0
1
10
8
6
6
6
1
0

The all-path matrix is used for the computation of the all-path Wiener index [326].

<< . . . >>