图 邻接矩阵的k次方

感觉挺有意思的这个小性质

使用一个矩阵来存储图，如下。（ a i j a_{i j} aij代表的是从 i i i到 j j j存在有一条边）。

A = [ 0 1 1 1 0 1 1 1 0 ] A = egin{bmatrix} 0&1&1\ 1&0&1\ 1&1&0 end{bmatrix} A=⎣⎡011101110⎦⎤

当把这个矩阵平方后，可以得到这样的一个矩阵。

B = A 2 = [ 2 1 1 1 2 1 1 1 2 ] B= A^2 = egin{bmatrix} 2&1&1\ 1&2&1\ 1&1&2 end{bmatrix} B=A2=⎣⎡211121112⎦⎤

根据矩阵乘法的定义，可以得到这样的式子（以 b 11 ,   b 12 b_{11},,b_{12} b11,b12为例）

b 11 = a 11 × a 11 + a 12 × a 21 + a 13 × a 31 b 12 = a 11 × a 21 + a 12 × a 22 + a 13 × a 23 b_{11} = a_{11} imes a_{11} + a_{12} imes a_{21} + a_{13} imes a_{31} \ b_{12} = a_{11} imes a_{21} + a_{12} imes a_{22} + a_{13} imes a_{23} b11=a11×a11+a12×a21+a13×a31b12=a11×a21+a12×a22+a13×a23

如果根据对 i j ij ij的定义的话，不难看出， a 11 × a 11 a_{11} imes a_{11} a11×a11指的是从 v 1 v_1 v1到 v 1 v_1 v1路径的情况。如果从 v 1 v_1 v1到 v 1 v_1 v1存在一条路的话，那么就可以从 v 1 v_1 v1走到 v 1 v_1 v1（也就是说 v 1 v_1 v1有一条能走到自己的路，并且只经过 v 1 v_1 v1）。同理，对于 a 12 × a 21 a_{12} imes a_{21} a12×a21，也是意味着从 v 1 v_1 v1走到 v 1 v_1 v1，中间经过了 v 2 v_2 v2的路径状况，再加上 a 13 × a 31 a_{13} imes a_{31} a13×a31，也就是说， b 11 b_{11} b11表示的是 v 1 v_1 v1-> v 1 v_1 v1-> v 1 v_1 v1、 v 1 v_1 v1-> v 2 v_2 v2-> v 1 v_1 v1、 v 1 v_1 v1-> v 3 v_3 v3-> v 1 v_1 v1这三条道路的状态总和。 b 12 b_{12} b12也是同理。

因此，对于邻接矩阵的平方，所得到的结果的 b i j b_{ij} bij表示从 v i v_i vi走到 v j v_j vj，经过一个节点的方案数。

那么再乘一次呢？

c 11 = b 11 × a 11 + b 12 × a 21 + b 13 × a 31 c_{11} = b_{11} imes a_{11} + b_{12} imes a_{21} + b_{13} imes a_{31} c11=b11×a11+b12×a21+b13×a31

显而易见，根据上面的推导，可以看得出，对于 b 11 × a 11 b_{11} imes a_{11} b11×a11，也就是在原来经过的结果上，再过一次 v 1 v_1 v1，其余的同理。

因此，若是邻接矩阵的 k k k次方，意味着（这里以 i j ij ij为例）从 v i v_i vi到 v j v_j vj，经过了 k k k个点的路径总数。