阿Q在一道真题中发现的结论：设G的邻接矩阵为A，则 A的n阶矩阵的元素 A^n [i][j] 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目。

题源

已知含有5个顶点的图G如下图：

1）写出图G的邻接矩阵A（行、列下标从0开始）

2）求A²，矩阵A²中位于0行3列元素值的含义是什么？

3）若已知具有 n (n >= 2) 个顶点的图的邻接矩阵为B，则 B^m (m <= 2 <= n) 中非零元素的含义是什么？

---

证明

1. 矩阵乘法的意义

矩阵$A^n$ 中的元素 $A^n[i][j]$

• $A^2[i][j] = \sum_{k} A[i][k] \cdot A[k][j]$，即从 $i$ 到 $j$ 经过一个中间节点 $k$ 的路径数目（长度为 2）。

• 同理，$A^n[i][j]$ 表示从 $i$ 到 $j$ 经过 $n-1$ 个中间节点的路径数目（长度为 $n$）。

2. 数学归纳法验证

• 基例：当 $n=1$，$A^1 = A$，显然 $A[i][j]$ 是长度为 1 的路径数。

• 归纳假设：假设 $A^k[i][j]$ 表示长度为 $k$ 的路径数。

• 递推：$A^{k+1} = A^k \cdot A$，则 $A^{k+1}[i][j] = \sum_{m} A^k[i][m] \cdot A[m][j]$，即从 $i$ 出发走 $k$ 步到 $m$，再走 1 步到 $j$，总步数为 $k+1$。对所有 $m$ 求和即总路径数。

3. 路径的允许情况

邻接矩阵的幂次计算包括所有可能的路径，允许重复访问节点或边。

4. 示例验证

• 简单环图：顶点 0→1→2→0，计算 A³ 得到单位矩阵，表明每个顶点到自身有一条长度为 3 的循环路径。
• 自环图：顶点 1 有自环，计算 A²[1][1]=2，对应路径 1→1→1 和 1→0→1。
• 不连通图：若顶点无出边，则高阶幂次为零矩阵，说明无对应长度路径。

---

实际用处

网络连通性分析

• 社交网络：
  假设想知道「用户A通过3个中间人能否联系到用户B」（类似六度空间理论），计算 A^4（4步路径）即可得到所有可能的4跳关系数量。
• 交通网络：
  计算城市之间的直达、转机路线。例如，A³[i][j] 表示从城市i出发，经过两次中转到达j的所有航班组合数。

通信与数据传输

• 路由器路径规划：
  在计算机网络中，数据包可能经过多个路由器转发。计算 A^n 可帮助评估不同路径的冗余度或负载均衡策略。
• 信号传播模型：
  在无线传感器网络中，信号可能通过多跳中继传递，矩阵幂次可量化不同跳数的信号覆盖路径数。