Path layer matrix

Path layer matrix --- матрица путевых слоёв.

The path layer matrix was introduced for simple graphs with the standard metric. Denote by [math]\displaystyle{ p(G) }[/math] the order of a graph [math]\displaystyle{ G }[/math] (the number of vertices). The path layer matrix of a graph [math]\displaystyle{ G }[/math] is the matrix

[math]\displaystyle{ \tau(G) = [\tau_{ij}], \; i = 1,2, \ldots, p(G), \; j = 1,2, \ldots, p(G)-1, }[/math]

where [math]\displaystyle{ \tau_{ij} }[/math] is the number of paths with the initial vertex [math]\displaystyle{ v_{i} }[/math] that have the length [math]\displaystyle{ j }[/math]. By ordering the rows of [math]\displaystyle{ \tau(G) }[/math], first by decreasing the length (the number of the last nonzero element) and then with rows of the same length arranged lexicographically, one obtains a canonical form for [math]\displaystyle{ \tau(G) }[/math].

Let [math]\displaystyle{ G }[/math] be a weighted graph and let [math]\displaystyle{ l_{1}, \ldots, l_{n} }[/math] be the possible lengths of paths in [math]\displaystyle{ G }[/math]. The path layer matrix of a weighted graph [math]\displaystyle{ G }[/math] is the matrix [math]\displaystyle{ \tau w(G) = [\tau w_{ij}], \; i = 1,2, \ldots, p(G), \; j = 1, 2, \ldots, n }[/math], where [math]\displaystyle{ \tau w_{ij} }[/math] is the number of paths with the initial vertex [math]\displaystyle{ v_{j} }[/math] that have the length [math]\displaystyle{ l_{j} }[/math].