图论：邻接矩阵、路径与环

IB 数学：应用与解释 HL· 单元5：统计与概率，主题12：图论· 15 分钟阅读

1. 构建邻接矩阵★☆☆☆☆⏱ 5 min

📘 定义

邻接矩阵

$A$ , $n \times n$ for $n$ vertices

元素 $A_{ij}$ 记录从顶点 $i$ 到顶点 $j$ 的边数。无向图的邻接矩阵是对称矩阵，有向图通常是非对称矩阵。

例:

三顶点无向三角形的所有非对角元素都等于1。

自环（起点和终点相同的边）记录在矩阵的主对角线上。邻接矩阵是一种紧凑、便于计算机处理的图信息存储方式，方便后续计算。

📐 例题

为顶点为 $V_{1}, V_{2}, V_{3}$ ，边为 $V_{1} \to V_{2}$ 、 $V_{1} \to V_{3}$ 、 $V_{2} \to V_{3}$ 、 $V_{3} \to V_{1}$ 的有向图构建邻接矩阵。

1
确认矩阵大小为 $3 \times 3$ ，行对应起点，列对应终点。
2
填充第1行（起点为 $V_{1}$ ）： $A_{11} = 0$ , $A_{12} = 1$ , $A_{13} = 1$
3
填充第2行（起点为 $V_{2}$ ）： $A_{21} = 0$ , $A_{22} = 0$ , $A_{23} = 1$
4
填充第3行（起点为 $V_{3}$ ）： $A_{31} = 1$ , $A_{32} = 0$ , $A_{33} = 0$
5
最终邻接矩阵：
6
$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$

2. 利用矩阵幂计数路径★★★☆☆⏱ 8 min

邻接矩阵的核心性质是： $A^{k}$ （A的k次幂）的 $(i, j)$ 元素等于顶点 $i$ 和顶点 $j$ 之间恰好包含k条边的不同路径的数量。该性质对有向图和无向图都成立。

📐 例题

对于上一个例子中的邻接矩阵，从 $V_{1}$ 到 $V_{3}$ 长度为2的路径有多少条？

1
计算 $A^{2} = A \times A$ ：
2
$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}$
3
起点为 $V_{1}$ （第1行），终点为 $V_{3}$ （第3列）的元素值为1。
4
恰好存在1条从 $V_{1}$ 到 $V_{3}$ 长度为2的路径： $V_{1} \to V_{2} \to V_{3}$ 。

✓ 快速检测

测试你对规则的理解：

$A^{2}$ 中 $(2, 1)$ 元素代表什么？
- 从 $V_{1}$ 到 $V_{2}$ 长度为2的路径数量
- 从 $V_{2}$ 到 $V_{1}$ 长度为2的路径数量
- 起点为 $V_{2}$ 长度为2的环的数量
显示答案
从$V_2$到$V_1$长度为2的路径数量 —
行始终对应起点，列始终对应终点，因此元素 $(i, j)$ 计数从i到j的路径。

3. 利用邻接矩阵识别环★★★☆☆⏱ 6 min

环是起点和终点相同的路径，因此所有长度为k的环都记录在 $A^{k}$ 的主对角线上。主对角线元素的和称为 $A^{k}$ 的迹，它给出整个图中长度为k的环的总数。

📘 定义

矩阵的迹

方阵主对角线上所有元素的和。对于 $A^{k}$ ， $tr (A^{k})$ 等于图中长度为 $k$ 的环的总数。

📐 例题

求前文提到的三顶点有向图中长度为2的环的总数。

1
我们已经得到 $A^{2}$ ，其对角元素为 $1, 0, 0$ 。
2
计算迹：
3
$\text{tr}(A^2) = 1 + 0 + 0 = 1$
4
恰好存在1条长度为2的环： $V_{1} \to V_{3} \to V_{1}$ 。

4. 实际应用★★☆☆☆⏱ 4 min

邻接矩阵可用于对各类网络建模：社交连接、交通路线、网站链接和供应链。路径计数有助于回答信息或货物如何在网络中流动的问题。

📐 例题

一个社交网络有3名用户：A、B、C。A关注B和C，B关注C，C关注A。从A出发的消息经过恰好2次关注关系转发后到达C，有多少种不同方式？

1
该网络与我们之前的示例图一致：A对应 $V_{1}$ ，B对应 $V_{2}$ ，C对应 $V_{3}$ 。
2
我们已经知道 $A^{2}$ 的 $(1, 3)$ 元素为1。
3
恰好存在1条路径：A → B → C。

5. 常见陷阱

错误做法:

有向图中交换行和列，将i到j的边错计为j到i的边。

原因:

IB采用的规则是行=起点，列=终点，颠倒会导致所有计数错误。

正确做法:

构建矩阵时始终将行标记为起点，列标记为终点。

错误做法:

将 $(A^{k})_{ij}$ 误解为长度不超过k条边的路径数，而非恰好k条边的路径数。

原因:

考试题目经常同时要求特定长度和累积长度的路径，混淆两者会导致答案错误。

正确做法:

恰好k条边用 $A^{k}$ ，不超过k条边则对 $A^{1}$ 到 $A^{k}$ 求和。

错误做法:

将自环视为零长度环，计算迹时忽略它们。

原因:

环至少需要一条边，因此自环是合法的长度为1的环。

正确做法:

计数任意长度的总环数时，将自环对应的对角元素包含在内。

错误做法:

多重图中即使两个顶点之间有多条边，仍将 $A_{ij}$ 设为1。

原因:

多条边对应多条不同的路径，因此必须明确计数。

正确做法:

将 $A_{ij}$ 设为i和j之间实际的边数，而不只是0或1。

6. 速查表

概念	邻接矩阵中的含义
元素 $A_{ij}$	从i到j的边数 / 长度为1的路径数
元素 $(A^{k})_{ij}$	从i到j恰好k条边的路径数
$A + A^{2} + ... + A^{k}$ 中的元素	从i到j不超过k条边的路径数
对角元素 $(A^{k})_{ii}$	起点/终点为i的长度为k的环数
$A^{k}$ 的迹	图中长度为k的环的总数
无向图的性质	$A = A^{T}$ (邻接矩阵是对称矩阵)

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2021 · 2
计数城镇之间的路径
2022 · 1
计数有向图中的环
2023 · 2
社交网络路径计数

深入阅读

syllabusIB AI HL 官方图论大纲本主题的官方大纲参考

下一步

邻接矩阵是你在IB AI HL中遇到的所有高级图论问题的基础，包括最短路径算法、连通分量分析和网络优化。路径和环的计数在试卷1（小型无需计算器的矩阵）和试卷2（需要计算器的大型矩阵问题）中都经常考查，因此掌握规则和矩阵乘法是获得满分的关键。除考试外，邻接矩阵也是计算机科学、网络分析、运筹学和数据科学中对各类连接系统建模的核心工具。