第十二课：图论、树¶
Page 2 — 正则图¶
- 所有顶点度数相同的图称为正则图
- Kₙ是(n-1)-正则图
Page 3 — 子图¶
- G₁=⟨V₁,E₁⟩, G₂=⟨V₂,E₂⟩
- V₁⊆V₂且E₁⊆E₂ → G₁是G₂的子图
- G₁≠G₂ → 真子图
- 生成子图：V₁=V₂（顶点相同）
Page 4 — 补图¶
- G₁和G₂互为补图：
- V₁=V₂, E₁∩E₂=∅
- ⟨V₁,E₁∪E₂⟩是完全图
Page 5-6 — 图的同构¶
- |V₁|=|V₂|, |E₁|=|E₂|
- 可通过对结点的置换使两图相同
- 不同构的例子：乙醇CH₃CH₂OH vs 甲醚CH₃OCH₃（图论中的同分异构体）
Page 7-9 — 路径与通路¶
| 术语 | 定义 |
|---|---|
| 拟路径 | 顶点和边的序列（允许重复顶点和边） |
| 路径（walk） | 边各不相同的拟路径 |
| 通路（path） | 顶点各不相同的路径 |
| 闭路径 | 起点=终点的路径 |
| 回路（cycle） | 起点=终点的通路 |
- 路径和通路定理：n个顶点的图中，若u到v有拟路径，则必有长度≤n-1的通路
Page 10 — 图的连通性¶
| 类型 | 定义 |
|---|---|
| 连通（无向图） | 任意两顶点互相可达 |
| 强连通（有向图） | 任意两顶点互相可达 |
| 单向连通（有向图） | 至少一个方向可达 |
| 弱连通（有向图） | 忽略方向后连通 |
Page 11 — 连通分支¶
- 图G的最大连通子图G'
Page 12-14 — 欧拉图与哈密顿图 ⭐¶
欧拉图（边不重复，过所有边）¶
- 欧拉图：存在经过所有顶点和所有边的闭路径
- 欧拉路径：存在经过所有顶点和所有边的路径（不一定回路）
充要条件： | 图类型 | 欧拉图（回路）| 欧拉路径 | |--------|-------------|---------| | 无向图 | 连通 + 所有顶点度均为偶数 | 连通 + 恰两个奇数度顶点 | | 有向图 | 弱连通 + 每个顶点出度=入度 | 弱连通 + 恰一个顶点出度=入度+1，一个入度=出度+1 |
哈密顿图（顶点不重复，过所有顶点）¶
- 哈密顿图：存在经过所有顶点的回路
- 哈密顿通路：存在经过所有顶点的通路
- 充分条件：n个顶点的图，每对顶点度数和≥n → 哈密顿图
- NP完全问题——没有高效算法
💡 人话： - 欧拉图关心边，问能不能"一笔画"走完所有边。条件是奇点数为0或2。 - 哈密顿图关心顶点，问能不能走完所有顶点不重复。是NP完全问题，没有好办法。
Page 16-19 — 邻接矩阵¶
- 邻接矩阵A[G]：|V|×|V|的0-1矩阵
- aᵢⱼ=1 ⟺ ⟨vᵢ,vⱼ⟩∈E
- 有向图的邻接矩阵不一定对称
- Aⁿ[i][j]：从vᵢ到vⱼ长度=n的路径数
Page 20-23 — 关联矩阵¶
- 关联矩阵M[G]：|V|×|E|的矩阵
- mᵢⱼ=1 ⟺ vᵢ是eⱼ的端点
- 每列恰有两个1（无向边对应两个端点）
Page 28-37 — 二分图与匹配¶
- 二分图：顶点可分成V₁和V₂，所有边都在V₁和V₂之间
- 匹配：边集的子集，无公共顶点
- 最大匹配：边数最多的匹配
- 增广路算法：从未匹配顶点出发找增广路，取对称差扩大匹配
- 应用：教师-课程分配问题
Page 38-41 — 平面图 ⭐¶
- 平面图：边可以画得只在顶点处相交
- K₅和K₃,₃都不是平面图
- K₅是顶点数最少的非平面图
- K₃,₃是边数最少的非平面图
- Kuratowski定理（1930）：G或其子图的同胚图不能以K₅或K₃,₃为子图
💡 人话：平面图就是能画在纸上不让边交叉的图。K₅（5个顶点全连接）和K₃,₃（3+3个顶点的完全二分图）是"最小"的不能画成平面图的图。
Page 42-46 — 树 ⭐¶
- 树：连通无回路的无向图
- 树叶：树中的悬挂点（度为1）
- 分支点：度>1的节点
- 森林：每个连通分支都是树
树的性质： - ✅ 简单图 - ✅ 二分图 - ✅ 平面图 - ⭐ |V| = |E| + 1（顶点比边多1） - 树中任意两顶点之间有唯一通路 - 任意连通图至少有一颗生成树（删回路上的边直到无回路）
根树： - 一个孤立节点v₀是根树 - T₁,...,Tₖ是根树，v₀是新根，连接v₀与各棵树根 → 新根树 - n元树：每个节点至多有n个子节点 - n元有序树：子节点规定了次序 - 二元有序树最常用：左子节点表示第一个子节点，右子节点表示下一个兄弟节点