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

> IB 数学：应用与解释 HL · IB AI HL
> 来源: https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-adjacency-matrices-paths/

本子主题介绍如何将图表示为矩阵，并利用矩阵幂计数顶点之间的路径、识别环。你将学习如何应用这些方法解决IB考试中常见的连接和路径规划问题。

**先修:** [矩阵运算与幂](https://www.owlsprep.com/zh/study/ib-math-ai-hl-matrix-operations-powers/); [基础图论术语](https://www.owlsprep.com/zh/study/ib-math-ai-hl-graph-theory-introduction/)

## 学习目标

- 为有向图和无向图构建邻接矩阵
- 利用矩阵幂计算顶点之间给定长度路径的数量
- 利用邻接矩阵幂的迹的性质计数环
- 应用邻接矩阵方法解决实际连接问题

## 构建邻接矩阵

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

*记法:* $A$, $n \times n$ for $n$ vertices

*例:* 三顶点无向三角形的所有非对角元素都等于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}$$

## 利用矩阵幂计数路径

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

> **tip**
>
> 若要统计长度不超过k条边的总路径数，对矩阵$A^1 + A^2 + ... + A^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$。

**概念自测**

测试你对规则的理解：

1. $A^2$中$(2,1)$元素代表什么？

   - 从$V_1$到$V_2$长度为2的路径数量
   - 从$V_2$到$V_1$长度为2的路径数量
   - 起点为$V_2$长度为2的环的数量

   *解析:* 行始终对应起点，列始终对应终点，因此元素$(i,j)$计数从i到j的路径。

## 利用邻接矩阵识别环

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

**矩阵的迹** — 方阵主对角线上所有元素的和。对于$A^k$，$\text{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$。

## 实际应用

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

**例题:** 一个社交网络有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。

## 常见错误

- **错误做法:** 有向图中交换行和列，将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。

## 速查表

| 概念 | 邻接矩阵中的含义 |
| --- | --- |
| 元素$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$ (邻接矩阵是对称矩阵) |

## 下一步

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

- [生成树与最小生成树算法](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/)
- [图论应用：中国邮路问题（CPP）和旅行商问题（TSP）](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-adjacency-matrices-paths/