学习目标
掌握定义、公式与定理条件；能使用原讲义中的真值表、矩阵、图表、分布和统计推断题完成练习。
第 7 章：图论
无向图写作 \(G=(V,E)\)，其中 \(V\) 是顶点集，\(E\) 是无序顶点对构成的边集；有向图（有向网络）中的边是有序对 \((u,v)\)，方向不能忽略。
1. 本章复习目标
2. 知识框架
概念与性质
先厘清定义、条件和性质的联系。
公式与应用
再用题型模板、例题和练习完成方法迁移。
3. 核心知识点
原讲义内容
1. 图与基本类型
无向图写作 \(G=(V,E)\)，其中 \(V\) 是顶点集，\(E\) 是无序顶点对构成的边集；有向图（有向网络）中的边是有序对 \((u,v)\)，方向不能忽略。
| 概念 | 定义或判断特征 | 考试提醒 |
|---|---|---|
| 简单图 ⭐⭐⭐ | 无环、无平行边。 | “顶点相邻”通常默认在简单无向图语境下。 |
| 多重图 ⭐⭐ | 允许同一对顶点之间有平行边；有的教材还允许环。 | 计算度数时，每条平行边都要计数；一个环对无向度数贡献 \(2\)。 |
| 完全图 \(K_n\) ⭐⭐ | 每对不同顶点之间恰有一条边，\(|E|=\frac{n(n-1)}2\)。 | 不要把完全图误解为“所有顶点都有环”。 |
| 子图、导出子图 ⭐⭐ | 子图取部分顶点、部分边；对 \(S\subseteq V\)，导出子图保留 \(S\) 内原有的全部边。 | 题目给“由顶点集导出”时，不能随意删边。 |
| 补图 \(\overline G\) ⭐⭐ | 对简单图，保留原图顶点；不同顶点在补图相邻，当且仅当在原图不相邻。 | \(G\) 与 \(\overline G\) 的边数之和为 \(\binom n2\)。 |
2. 度与握手定理
无向图中顶点 \(v\) 的度 \(\deg(v)\) 是与它关联的边数。有向图中，入度 \(\deg^-(v)\) 数入边，出度 \(\deg^+(v)\) 数出边。
\[\sum_{v\in V}\deg(v)=2|E|,\qquad \sum_{v\in V}\deg^+(v)=\sum_{v\in V}\deg^-(v)=|E|.\]
握手定理为什么成立？
无向图每条边有两个端点，统计所有顶点的度时，这条边在两个端点各贡献 \(1\)，故总共恰被数两次，得到 \(2|E|\)。因此奇度顶点的个数必为偶数：若奇度顶点有奇数个，所有度数之和会是奇数，和 \(2|E|\) 矛盾。
练习 1：无向图的度数依次为 \(3,3,2,2,2\)，它有多少条边？奇度顶点数是否合理？
思路：先用握手定理求边数；再检查奇度顶点个数。
过程：度数和为 \(3+3+2+2+2=12=2|E|\)，所以 \(|E|=6\)。奇度顶点有两个，确为偶数。
答案：\(\boxed{|E|=6}\)，该度序列未违反握手定理。
易错点：握手定理只给必要条件，度数和为偶数不自动保证一定存在这样的简单图。
3. 通路、回路与连通性
本页采用常见约定：通路是不重复边的顶点—边交替序列；简单通路还要求顶点不重复；首尾相同的通路为回路；除起止顶点外无重复顶点的回路为简单回路。不同教材可能把“通路”称为“迹”，作答前以题目约定为准。
| 概念 | 判断方法 |
|---|---|
| 无向图连通 ⭐⭐⭐ | 任意两顶点间存在通路；从任一顶点做 DFS/BFS 能访问所有顶点。 |
| 连通分支 ⭐⭐⭐ | 极大的连通子图。每个顶点恰属于一个连通分支；数分支可用多次 DFS/BFS。 |
| 强连通（有向图） ⭐⭐⭐ | 任意 \(u,v\) 都存在 \(u\leadsto v\) 与 \(v\leadsto u\) 的有向通路。只“忽略方向后连通”并不够。 |
判连通模板：
- 任选未访问顶点作为起点，沿边访问所有可达顶点。
- 若所有顶点均被访问，无向图连通；否则已访问部分形成一个分支。
- 换一个未访问顶点重复，起点次数就是连通分支数。对有向图的强连通性，要同时考虑正向与反向可达。
4. Euler 图与 Hamilton 图
Euler：研究“边” ⭐⭐⭐
Euler 路经过每条边恰一次；Euler 回路经过每条边恰一次且回到起点。
对无向连通图：存在 Euler 回路 \(\Longleftrightarrow\) 所有顶点度均为偶数；存在 Euler 路 \(\Longleftrightarrow\) 奇度顶点恰有 \(0\) 或 \(2\) 个。
Hamilton：研究“顶点” ⭐⭐⭐
Hamilton 路经过每个顶点恰一次；Hamilton 回路经过每个顶点恰一次并回到起点。
没有像 Euler 条件那样简单的充要度数判据。若简单图 \(n\ge3\) 且每点度至少 \(n/2\)，Dirac 定理保证存在 Hamilton 回路，但它只是充分条件。
Euler 条件为何正确：走到一个中间顶点时，每次“进入”必须配一条尚未使用的“离开”边，所以中间顶点度数为偶数。若路不闭合，只有起点和终点可各多出一条未配对的边，故恰有两个奇度顶点；闭合时连起终也配对，故无奇度顶点。
练习 2：连通图的顶点度为 \(4,2,2,2,2\)，能否一笔画回到起点？若度为 \(3,3,2,2\) 呢？
思路：只需数奇度顶点，并先确认题目给出连通。
过程：第一组全为偶数，存在 Euler 回路。第二组有两个奇度顶点，存在 Euler 路但起点、终点必须是两个奇度顶点，不能形成 Euler 回路。
答案：第一组 \(\boxed{\text{可一笔回到起点}}\)；第二组 \(\boxed{\text{只能一笔走完，不能回到起点}}\)。
练习 3：为什么 \(K_{3,4}\) 没有 Hamilton 回路，却有 Hamilton 路？
思路：\(K_{3,4}\) 是二分图，任何回路必须在两个部分之间交替。
过程：Hamilton 回路若经过所有 \(7\) 个顶点，交替序列回到起点时两部分使用数必须相等；但两部分大小为 \(3,4\)，矛盾。Hamilton 路可以从大小为 \(4\) 的一侧开始，也在这一侧结束，交替经过 \(4+3\) 个顶点。
答案：\(\boxed{\text{无 Hamilton 回路，有 Hamilton 路}}\)。
5. 平面图与矩阵表示
连通平面图的 Euler 公式：\[\boxed{v-e+f=2}\]其中 \(v,e,f\) 分别是顶点、边、面（含外部面）数。
对 \(v\ge3\) 的简单连通平面图，因每个面边界至少有三条边且每条边至多邻接两个面，得 \(e\le3v-6\)。若图违反此不等式，就不可能是平面图；满足它却不保证一定平面。
| 表示 | 构造与用途 | 关键性质 |
|---|---|---|
| 邻接矩阵 \(A\) ⭐⭐⭐ | \(a_{ij}=1\) 表示 \(v_i,v_j\) 相邻；多重图可填边数。 | 简单无向图矩阵对称、主对角为 \(0\)；\(A^k\) 的 \((i,j)\) 项计数长度 \(k\) 的走法数。 |
| 关联矩阵 \(B\) ⭐⭐ | 行对应顶点、列对应边；无向图中一条普通边所在列有两个 \(1\)。 | 用来读“哪条边连接哪些顶点”；有向图常用 \(-1,1\) 分别标记起点、终点。 |
| 可达矩阵 \(P\) ⭐⭐⭐ | \(p_{ij}=1\) 表示存在 \(v_i\leadsto v_j\) 的通路。 | 把长度 \(0\) 的自身可达也计入时，\(P=I\lor A\lor A^2\lor\cdots\lor A^{n-1}\)（布尔运算）；强连通时 \(P\) 全为 \(1\)。 |
练习 4：图 \(V=\{1,2,3,4\},E=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\}\}\)，写邻接矩阵。
思路：按顶点顺序 \(1,2,3,4\)，第 \(i\) 行第 \(j\) 列写 \(i,j\) 是否相邻。
答案：
A = [ 0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0 ]
易错点：无向图要同时填 \(a_{ij}\) 与 \(a_{ji}\)；简单图主对角线不填 \(1\)。
4. 常见题型
方法选择
原讲义中的判断方法、真值表、矩阵、图示、分布或统计计算流程均已完整保留在“核心知识点”区。
5. 典型例题
例题使用方式
先独立作答，再核对原讲义中的关键推导、公式条件与答案。
6. 练习题
练习与解析
原有折叠练习、完整解析与易错提示均保留在“核心知识点”区。
7. 易错点
8. 公式速查
| 复习顺序 | 使用要求 | 检查项 |
|---|---|---|
| 定义与定理 | 确认适用条件 | 对象、范围、已知条件 |
| 公式与计算 | 代入前保持符号一致 | 量词、集合符号、矩阵维数或概率参数 |
| 结论 | 说明结论范围 | 结果、逻辑方向与单位 |
9. 本章总结
必须记忆
核心定义、公式和定理条件。
必须理解
概念间的区别与方法选择依据。
必须会做
原讲义中的例题、练习与综合题型。
容易丢分
忽略前提、符号不严谨、混淆相近概念或跳过关键步骤。