# 图论：基本概念

> IB 数学 AI HL · IB 数学 AI HL
> 来源: https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-basic-concepts/

本子主题介绍了图论的核心基础构件，图论是用于建模对象间关系的离散数学工具。你将学习适用于IB AI HL的核心术语、图分类，以及支撑所有图论应用的基本性质。

**先修:** [基础矩阵运算与记号](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u2-matrix-operations/)

## 学习目标

- 识别并定义图的核心组成部分：顶点、边、环和度数
- 按类型对图进行分类（无向/有向、简单/非简单、加权/无权）
- 应用握手引理关联顶点度数与边的数量
- 使用邻接矩阵和邻接表表示图

## 图的核心组成

**图** — 一种由表示对象的顶点（节点）集合$V$，以及连接顶点对以表示对象间关系的边集合$E$构成的数学结构。

*记法:* G = (V, E)

*例:* 图可以用来对社交媒体用户（顶点）和好友关系（边）建模。

除了基本图结构外，你必须记住以下几个考试核心术语：

- - **顶点（节点）**：表示对象的单个点，通常标记为$A, B, C$。
- - **边**：两个顶点之间的连接；边可以是无向的（双向的）或有向的（单向的）。
- - **环**：连接顶点到自身的边。
- - **顶点的度数**：连接到该顶点的边的数量；一个环对度数的贡献为2。

**例题:** 对于顶点为$A, B, C$，边为$AB, AC, BC, CC$（$C$处有一个环）的无向图，求每个顶点的度数。

1. 统计连接到顶点$A$的边：$A$有2条边，因此：
2. $$\deg(A) = 2$$
3. 统计连接到顶点$B$：$B$有2条边，因此：
4. $$\deg(B) = 2$$
5. 统计连接到顶点$C$：$C$有2条普通边加1个环。环为度数加2，因此：
6. $$\deg(C) = 1 + 1 + 2 = 4$$

## 图的分类

图根据边的性质和结构进行分类，IB AI HL最常考的分类如下：

**简单图** — 简单无向图没有环，且同一对顶点之间没有多重边。大多数基础图论问题都使用简单图。

- - **无向图**：边没有方向，关系是双向的（例如好友关系）。
- - **有向图（digraph）**：边有从一个顶点指向另一个顶点的方向（例如社交媒体的单向关注）。
- - **加权图**：每条边都有一个对应的数值权重（例如两个城市之间的距离）。
- - **连通图**：任意一对顶点之间都存在路径，没有孤立分量。

**例题:** 对建模城市4个交叉口之间单向街道网络的图进行分类。

1. 街道是单向的，因此边有明确的从一个交叉口到另一个交叉口的方向。
2. 同一对交叉口之间可能存在多条单向街道，因此该图不是简单图。
3. 如果图将每条街道的长度作为数值，那么它同时也是加权图。结论：
4. 该图是连通、有向、非简单（加权）图。

> **考试提示:** 对简单图分类时一定要检查是否存在环——即使只有一个环，该图也不能是简单图。

## 握手引理

握手引理是所有无向图的基本性质，它关联了顶点度数之和与总边数。

**握手引理** — 对于任意无向图，所有顶点的度数之和等于边数的两倍。该结论成立是因为每条边对总度数和的贡献恰好为2，它连接的两个顶点各得1。

*记法:* \sum_{v \in V} \deg(v) = 2|E|

**例题:** 一个无向简单图有4个顶点，度数分别为1、2、3和2，该图有多少条边？

1. 首先，计算所有顶点度数之和：
2. $$1 + 2 + 3 + 2 = 8$$
3. 应用握手引理：度数和等于边数的两倍：
4. $$8 = 2|E|$$
5. 求解$|E|$（边的数量）：
6. $$|E| = 4$$

**概念自测**

测试你的理解：

1. 一个无向图能否有5个顶点，所有顶点的度数都是奇数？

   - 是
   - 否

   *答案:* 否

   *解析:* 5个奇数的和是奇数。握手引理要求度数和等于$2|E|$，而$2|E|$一定是偶数，因此这种情况不可能存在。

## 图的表示方法

图可以通过两种常见的可考数值格式表示：邻接矩阵和邻接表。

**邻接矩阵** — 对于有$n$个顶点的图，邻接矩阵是一个$n \times n$矩阵，其中元素$A_{ij}$是顶点$i$和顶点$j$之间的边数。对于有向图，$A_{ij}$是从$i$到$j$的边数。

*记法:* A

**例题:** 写出顶点为$V = \{A, B, C\}$，边为$AB, AC, CC$的无向图的邻接矩阵。

1. 顶点排序为$A$（第1行）、$B$（第2行）、$C$（第3行）。通过统计每对顶点之间的边数填写元素：
2. $A$连接到$B$和$C$，没有环：$A_{11}=0, A_{12}=1, A_{13}=1$
3. $B$连接到$A$和$C$，没有环：$A_{21}=1, A_{22}=0, A_{23}=1$
4. $C$连接到$A$、$B$，且有一个环：$A_{31}=1, A_{32}=1, A_{33}=1$（邻接矩阵中环的元素计数为1）
5. 最终的邻接矩阵为：
6. $$\begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}$$

邻接表是稀疏图的一种更简单的表示方法：它列出每个顶点及其所有邻接顶点。对于上述例子，邻接表为：$A: [B, C], \quad B: [A, C], \quad C: [A, B, C]$。

## 常见错误

- **错误做法:** 将环对顶点度数的贡献计为1而非2
  - 原因: 握手引理要求每条边对总度数的贡献为2，环也不例外，因为环的起点和终点都是同一个顶点
  - 正确做法: 统计环时，始终给顶点度数加2
- **错误做法:** 假设考试中所有图都是没有环和多重边的简单图
  - 原因: 考题经常给出非简单图，错误分类会导致度数统计和邻接矩阵元素错误
  - 正确做法: 开始计算前，始终明确检查是否存在环和多重边
- **错误做法:** 混淆有向图邻接矩阵的行和列
  - 原因: 元素定义为从行顶点到列顶点的边，颠倒会得到错误的连接关系
  - 正确做法: 对于有向图，确认$A_{ij}$表示从行顶点$i$到列顶点$j$的边
- **错误做法:** 认为无向图度数和为奇数是合法的
  - 原因: 握手引理要求度数和为偶数，因为它等于边数的两倍
  - 正确做法: 如果得到奇数和，重新检查度数统计，通常是环的计数错误
- **错误做法:** 认为无向图的邻接矩阵非对称是合法的
  - 原因: 如果一条边连接$A$到$B$，它也连接$B$到$A$，因此矩阵必须关于主对角线对称
  - 正确做法: 如果无向图的邻接矩阵不对称，说明你的元素填写有误

## 速查表

| 术语 | 核心规则/定义 | 记号 |
| --- | --- | --- |
| 图 | 顶点集合 + 边集合 | $G=(V,E)$ |
| 顶点度数 | 连接边数；环贡献为2 | $\deg(v)$ |
| 握手引理 | 度数和 = 2 × 边数 | $\sum \deg(v) = 2\|E\|$ |
| 简单图 | 无环，无多重边 | n/a |
| 邻接矩阵 | $n \times n$矩阵，元素为$i,j$之间的边数 | $A_{ij}$ |
| 有向图 | 边为单向 | Digraph |
| 加权图 | 边带有对应的数值权重 | n/a |

## 下一步

基本图概念是IB AI HL所有后续图论主题的基础，你将应用这些概念解决实际优化问题。你在这里学到的术语和表示方法是所有后续图论主题的必备基础，因此掌握这些基础知识会让你更容易应对更高级的问题。接下来，你将学习寻找图中的路径和回路，这类知识用于解决路径规划和网络设计等问题。之后，你将学习最小生成树和最短路径算法，这些都是常见的考题，完全依赖于对基本图组成的正确理解。

- [图论：邻接矩阵、路径与环](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-adjacency-matrices-paths/)
- [生成树与最小生成树算法](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-basic-concepts/