邻接矩阵自乘性质

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 的可能路径数量。

证毕。

Leave a Comment