题目

已知含有 5 个顶点的图 G 如下图所示。

请回答下列问题：

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

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

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

解析

(1) 邻接矩阵 A

答案：

逐行核对（边 0-1, 0-2, 0-4, 1-3, 1-4, 2-3, 3-4，无向图对称）：

• 顶点 0 的邻居：1, 2, 4 → 第 0 行 [0, 1, 1, 0, 1]
• 顶点 1 的邻居：0, 3, 4 → 第 1 行 [1, 0, 0, 1, 1]
• 顶点 2 的邻居：0, 3 → 第 2 行 [1, 0, 0, 1, 0]
• 顶点 3 的邻居：1, 2, 4 → 第 3 行 [0, 1, 1, 0, 1]
• 顶点 4 的邻居：0, 1, 3 → 第 4 行 [1, 1, 0, 1, 0]

(2) A² 与 A²[0][3] 的含义

答案：A² 如下，A²[0][3] = 3，含义是"从顶点 0 到顶点 3 长度为 2 的路径数 = 3 条"（分别经过中间顶点 1、2、4）。

A²[i][j] 的算法：。每个被乘项 等于 1 ⟺ 同时存在边 (i,k) 和 (k,j)，即"经过中间顶点 k 的长度 2 路径"。求和就是所有这种 2 步路径的数量。

算 A²[0][3] 演示：

k			乘积	含义
0	0	0	0	—
1	1	1	1	路径 0 → 1 → 3
2	1	1	1	路径 0 → 2 → 3
3	0	0	0	—
4	1	1	1	路径 0 → 4 → 3

A²[0][3] = 0 + 1 + 1 + 0 + 1 = 3——即从 0 到 3 共有 3 条长度为 2 的路径。

顺带核对对角线： 等于顶点 i 的度数（顶点 i 走出去再回来的 2 步路径，必然走"i → 邻居 → i"，共 deg(i) 条）。本图度数 [3, 3, 2, 3, 3] 与 A² 对角线 [3, 3, 2, 3, 3] 完全一致，验证 A² 计算正确。

(3) Bᵐ 中非零元素的含义

答案： 表示在原图中"从顶点 i 出发，恰好经过 m 条边到达顶点 j 的路径条数"。

为什么这个含义对？ 由数学归纳法（对幂次 m 归纳）：

• m = 1： ∈ {0, 1}，恰好就是"从 i 到 j 长度为 1 的路径数（0 或 1 条）"；
• m → m+1：。 是"i 到 k 走 m 步的路径数"， 是"k 到 j 走 1 步是否可达"，相乘后求和即"先走 m 步到 k、再走 1 步到 j"的所有方案——正好是 i 到 j 走 m+1 步的总路径数。

注意（区分易错点）：

• 这里的"路径"允许重复经过同一顶点和重复使用同一条边（图论里更准确的说法是"游走 walk"，不是简单路径 simple path）。例如 0 → 1 → 0 → 1 是 0 到 1 长度 3 的合法路径。
• 题面把矩阵幂次限定到 ，是因为 m = 1 时含义平凡（就是是否有边），且超过 n 步的路径不再有"几何意义"上的紧凑表达。

编者注（生僻术语）：「邻接矩阵的幂表示路径数」是图论与线性代数的经典联系。直接由矩阵乘法定义按定义展开就能证明，不需要图论的高级结论。考场写答案时，最简版本是「 表示 i 到 j 长度恰好为 m 的路径数」，可加一句"路径允许走重复顶点"作严谨补充。