图论基础

图论是离散结构分析的核心工具。学完本章应掌握：

1. 读懂图的结构参数（度、连通、路径）；
2. 使用核心定理进行判定与计数；
3. 通过例题建立“定义-定理-应用”链路。

1. 图与基本术语

设图 $G=(V,E)$：

• $V$：顶点集，$E$：边集。
• 无向图：边无方向；有向图：边有方向。
• 简单图：无重边、无自环。

1.1 度与邻接

• 无向图中顶点 $v$ 的度记为 $d(v)$。
• 有向图中有入度 $d^-(v)$ 与出度 $d^+(v)$。

定理 1（握手定理）

无向图满足：

$$\sum_{v\in V} d(v)=2|E|.$$

例题 1（握手定理计算）

某无向图有 12 条边，已知 4 个顶点度为 $1,2,4,5$，其余顶点度和为多少？

解： 总度数为 $2\times12=24$，已知和为 $12$，故其余顶点度和也是 $12$。

2. 路径、回路与连通

• 路径：顶点序列相邻有边。
• 简单路径：顶点不重复。
• 回路：起点终点相同的路径。
• 连通图：任意两顶点之间存在路径。

例题 2（连通性判定）

图由两个三角形组成且无公共顶点、无连接边，是否连通？

解： 不连通，因为跨两个三角形的任意顶点对之间不存在路径。

3. 树与生成树

• 树：连通且无环的无向图。
• 生成树：连通图的一个包含全部顶点的树形子图。

定理 2（树的等价刻画）

对 $n$ 个顶点的无向图，以下命题等价：

1. 是树；
2. 连通且有 $n-1$ 条边；
3. 无环且有 $n-1$ 条边；
4. 任意两点间有唯一简单路径。

例题 3（树判定）

图有 8 个顶点 7 条边，且连通。问是否为树？

解： 满足“连通 + 边数 $n-1$”，故是树。

4. 二分图

4.1 定义

图 $G$ 若顶点集可分为 $X,Y$，使每条边都连接 $X$ 与 $Y$ 中的点，则称 $G$ 为二分图。

定理 3

图是二分图当且仅当它不含奇环。

例题 4（奇偶环判定）

$C_5$ 与 $C_6$ 是否为二分图？

解： $C_5$ 是奇环，不是二分图；$C_6$ 是偶环，是二分图。

5. 欧拉路与欧拉回路

• 欧拉路：经过每条边恰好一次的路。
• 欧拉回路：起终点相同的欧拉路。

5.1 判定定理（欧拉定理）

定理 4（无向图）：连通无向图 $G$ 具有欧拉回路，当且仅当 $G$ 的所有顶点度数均为偶数。具有欧拉路但无欧拉回路，当且仅当 $G$ 恰有 2 个奇度顶点。

定理 5（有向图）：弱连通有向图具有欧拉回路，当且仅当每个顶点的入度等于出度。

5.2 构造算法：Hierholzer 算法

核心思想是不断在图中寻找子回路并拼接。其复杂度为 $O(|E|)$，是求解欧拉回路的标准算法。

6. 哈密顿图 (Hamiltonian Graphs)

• 哈密顿路：经过每个顶点恰好一次的路。
• 哈密顿回路：经过每个顶点恰好一次的回路。

6.1 判定定理（充分条件）

与欧拉图不同，哈密顿图的判定是 NP-完全问题，目前仅有充分条件：

• Dirac 定理：若 $n \ge 3$ 且每个顶点的度 $d(v) \ge n/2$，则 $G$ 是哈密顿图。
• Ore 定理：若 $n \ge 3$ 且对于每一对不相邻顶点 $u, v$，都有 $d(u)+d(v) \ge n$，则 $G$ 是哈密顿图。

7. 平面图与着色

7.1 平面图 (Planar Graphs)

若图能画在平面上且边仅在顶点处相交，则称平面图。

欧拉公式：连通平面图中，$V - E + F = 2$，其中 $F$ 为面数。

7.2 图着色

对顶点染色使相邻点颜色不同，所需最少颜色数称为色数 $\chi(G)$。

• 四色定理：平面图的色数 $\chi(G) \le 4$。

8. 本章练习

练习 1：握手定理进阶

一个 3-正则图（每个点度数均为 3）有 15 条边，求顶点数。

Check Solution

$3V = 2 \times 15 \implies V = 10$。

练习 2：欧拉判定

证明：若一个连通无向图中有 $2k$ 个奇度顶点，则最少需要 $k$ 条路径才能覆盖所有边（每条边恰好一次）。

Check Solution

可以通过添加 $k$ 条虚拟边连接奇度顶点对，构造欧拉回路。撤销这些边后，回路断裂为 $k$ 条路径。

练习 3：哈密顿图判定

$K_{3,3}$（完全二分图）是否是哈密顿图？

Check Solution

是。$n=6$，每个点度数为 3，满足 $d(v) \ge 6/2 = 3$ (Dirac 定理)。路径示例：$x_1 \to y_1 \to x_2 \to y_2 \to x_3 \to y_3 \to x_1$。

练习 4：平面图应用

一个平面图有 20 个顶点，每个顶点的度数均为 3。求它将平面分成了多少个区域（面）？

Check Solution

$V=20$。$2E = 3 \times 20 \implies E = 30$。 由欧拉公式 $F = E - V + 2 = 30 - 20 + 2 = 12$。

7. 学习闭环

• 后续专题：最短路算法
• 配套题单：离散数学练习库