问题描述
证明：图G中顶点$v_i$到顶点$v_j$之间长度为k的路径数量等于$A^k$的第(i,j)个元素，其中A是图G的邻接矩阵。
证明
证明k=1时成立
取k=1，显然图G中顶点$v_i$到顶点$v_j$之间长度为1的路径数量等于$A$的第(i,j)个元素，A为邻接矩阵
假设k=m的时候成立
假设k=m时成立，即
$$
A^m=(a^{m}{ij}){n*n}(i=1-n,j=1-n)
$$
矩阵中$a^{m}_{ij}$值等于图G中顶点$v_i$到顶点$v_j$之间长度为m的路径数量成立
证明k=m+1时成立
$$
A^{m+1}=(a^{m+1}{ij}){n*n}(i=1-n,j=1-n)
$$
其中$a^{m+1}{ij}=\sum{p=1}^n(a^{m}{ip}*a{pj})$
已知$a^{m}{ip}$数值等于顶点$v_i$到顶点$v_p$之间长度为m的路径数量，$a{pj}$为顶点$v_p$到顶点$v_j$之间长度为1的路径数量，两者乘积为顶点$v_i$经顶点$v_p$到顶点$v_j$长度为m+1的路径数量，求和即为顶点$v_i$到顶点$v_j$之间长度为m+1的所有路径数量，因此k=m+1时结论成立
至此，结论得证
