The detour-path matrix, denoted by pDM, is similarly defined as the vertex-distance-path matrix, that is, the matrix pDM is a square symmetric V × V matrix whose off-diagonal elements i,j count all paths of any length that are included within the longest path between vertex i and j [218]. Each element i,j of the pDM is computed from the corresponding detour matrix as follows:
[pDM]ij= |
|
||||
0 otherwise (67) |
The detour-path matrix of G1 (see structure A in Figure 2) is given below.
pDM(G1)= |
0 |
1 |
3 |
15 |
10 |
15 |
21 |
||
1 |
0 |
1 |
10 |
6 |
10 |
15 |
|||
3 |
1 |
0 |
6 |
3 |
6 |
3 |
|||
15 |
10 |
6 |
0 |
6 |
4 |
6 |
|||
10 |
6 |
3 |
6 |
0 |
6 |
10 |
|||
15 |
10 |
6 |
4 |
6 |
0 |
1 |
|||
21 |
15 |
10 |
6 |
10 |
1 |
0 |
The hyper-detour index can be obtained from the detour-path matrix. For acyclic graphs, the detour-path matrix is equal to the distance-path matrix and consequently, the hyper-detour index for acyclic graphs is equal to the hyper-distance-path index obtained from the distance-path matrix.