图论：基本概念

IB 数学 AI HL· 5 分钟阅读

1. 图的核心组成★☆☆☆☆⏱ 15 min

📘 定义

图

G = (V, E)

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

例:

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

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

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

📐 例题

对于顶点为 $A, B, C$ ，边为 $A B, A C, B C, C C$ （ $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$

2. 图的分类★☆☆☆☆⏱ 15 min

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

📘 定义

简单图

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

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

📐 例题

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

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

Exam tip:

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

3. 握手引理★★☆☆☆⏱ 20 min

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

📘 定义

握手引理

\sum_{v \in V} \deg(v) = 2|E|

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

📐 例题

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

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

✓ 快速检测

测试你的理解：

一个无向图能否有5个顶点，所有顶点的度数都是奇数？
- 是
- 否
显示答案
1 —
5个奇数的和是奇数。握手引理要求度数和等于 $2∣ E ∣$ ，而 $2∣ E ∣$ 一定是偶数，因此这种情况不可能存在。

4. 图的表示方法★★★☆☆⏱ 20 min

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

📘 定义

邻接矩阵

A

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

📐 例题

写出顶点为 $V = {A, B, C}$ ，边为 $A B, A C, C C$ 的无向图的邻接矩阵。

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], B : [A, C], C : [A, B, C]$ 。

5. 常见陷阱

错误做法:

将环对顶点度数的贡献计为1而非2

原因:

握手引理要求每条边对总度数的贡献为2，环也不例外，因为环的起点和终点都是同一个顶点

正确做法:

统计环时，始终给顶点度数加2

错误做法:

假设考试中所有图都是没有环和多重边的简单图

原因:

考题经常给出非简单图，错误分类会导致度数统计和邻接矩阵元素错误

正确做法:

开始计算前，始终明确检查是否存在环和多重边

错误做法:

混淆有向图邻接矩阵的行和列

原因:

元素定义为从行顶点到列顶点的边，颠倒会得到错误的连接关系

正确做法:

对于有向图，确认 $A_{ij}$ 表示从行顶点 $i$ 到列顶点 $j$ 的边

错误做法:

认为无向图度数和为奇数是合法的

原因:

握手引理要求度数和为偶数，因为它等于边数的两倍

正确做法:

如果得到奇数和，重新检查度数统计，通常是环的计数错误

错误做法:

认为无向图的邻接矩阵非对称是合法的

原因:

如果一条边连接 $A$ 到 $B$ ，它也连接 $B$ 到 $A$ ，因此矩阵必须关于主对角线对称

正确做法:

如果无向图的邻接矩阵不对称，说明你的元素填写有误

6. 速查表

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

真题中的出现

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

2021 · 1
构建图的邻接矩阵
2022 · 2
应用握手引理求边数
2023 · 1
按类型对图进行分类

下一步

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