1.n次方意义
当图 G 的邻接矩阵为 \(\textbf{A}\) ，则 \(\textbf{A}^n\) 的元素 \(\textbf{A}^n[i][j]\) 代表由顶点 i 至 顶点 j 的长度为 n 的路径数目。
1.1 证明
对 \(n = 2\) 有
\begin{align}
\textbf{A}^n = \sum_{k = 1}^{w}\textbf{A}[i][k]*\textbf{A}[k][j]
\end{align}
其中 w 是 矩阵 \(\textbf{A}\) 的阶。上式意味着把所有一步由节点 i 至任意节点 k ，且再由此节点 k 能一步至节点 j 的所有可能数量相加。换言之则是计算了所有2步从节点 i 至节点 j 的可能路径数量。
假设 \(n = n_t\) 时，\(\textbf{A}^{n_t}\) 满足所要的意义。则此时对于 \(n = n_t + 1\)
\begin{align}
\textbf{A}^{n_t+1} = \sum_{k = 1}^{w}\textbf{A}[i][k]*\textbf{A}^{n_t}[k][j]
\end{align}
上式意味着把所有一步由节点 i 至任意节点 k ，且再由此节点 k 能 \(n_t\) 步至节点 j 的所有可能数量相加。换言之则是计算了所有 \(n_t +1 \) 步从节点 i 至节点 j 的可能路径数量。
证毕。