四个总问题
① 这个图是什么？
第1章：基本概念、图的类型、度、路、圈、补图、同构等。
② 这个图连得稳不稳？
第2–4章：树、连通度、Euler/Hamilton，研究“能不能通”“怎么走”。
③ 这个图能不能拆 / 配 / 画？
第5–6章：匹配、因子分解、平面嵌入。
④ 这个图能不能分色？
第7章：边着色、点着色、色多项式。
GRAPH THEORY · GLOBAL REVIEW
图论第 1—7 章总复习：把零散章节连成一张知识网
这份汇总版不是简单把七章再抄一遍，而是把它们之间的依赖关系、共用概念、证明套路和做题入口串起来。目标是让你看到：图论不是 7 个分散专题，而是一条从基础结构 → 连通与回路 → 特殊结构 → 平面与着色逐层展开的主线。
第1章 图的基础
第2章 树
第3章 连通度
第4章 Euler / Hamilton
第5章 匹配与因子分解
第6章 平面图
第7章 图的着色
00
先看全局：七章其实在回答哪几类问题？
整本书的主线流程图
图的基本对象
点、边、度、路、圈
点、边、度、路、圈
→
特殊结构
树、二部图、完全图
树、二部图、完全图
→
连通与可达
割点、割边、κ、λ
割点、割边、κ、λ
→
回路问题
Euler / Hamilton
Euler / Hamilton
→
组合分解
匹配、因子
匹配、因子
→
平面约束
Euler 公式、对偶
Euler 公式、对偶
→
着色与计数
χ, χ′, Pₖ(G)
χ, χ′, Pₖ(G)
01
七章主线串联：每一章到底在整本书里负责什么
Chapter 1
图的基本概念：全书的字典
你后面所有章节都默认已经掌握这里的语言。
- 核心词：顶点、边、度、度序列、子图、导出子图、补图、路、迹、圈、连通、二部图、同构。
- 作用：给后续所有定理提供对象和记号。
- 最关键桥梁：“度”“路/圈”“连通”会贯穿后面全部章节。
Chapter 2
树：最简单但最重要的连通结构
树就是“无圈且刚好连通”的极简模型。
- 核心词：树、生成树、叶子、支撑子图。
- 典型结论：树的等价定义、n 阶树有 n−1 条边。
- 作用：它是第3章连通度、第6章平面图、第7章色多项式中的基础案例。
Chapter 3
连通度：图被破坏后还能不能保持联通
从“连通/不连通”升级到“连得有多稳”。
- 核心词：割点、割边、块、点连通度 κ(G)、边连通度 λ(G)。
- 作用：为第4章“能不能走遍”、第6章“面边界是圈”提供结构前提。
- 桥梁：很多强结论都需要 2-连通、k-连通 作为前提。
Chapter 4
Euler / Hamilton：关于“走一遍”和“走一圈”
这是整本书第一次真正进入“全局回路”问题。
- Euler：关心边——每条边恰好一次。
- Hamilton：关心点——每个点恰好一次。
- 作用：把“度”“连通”“圈”等基本概念整合成大问题。
Chapter 5
匹配与因子分解：关于“配对”和“拆分”
它把“边的局部选择”变成“全图分解”。
- 匹配：选互不相邻的边。
- 完美匹配：所有点都被配上。
- 因子：把整张图分成若干结构规则的生成子图。
- 作用：与第7章边着色强关联，因为“同色边集就是匹配”。
Chapter 6
平面图：当图必须“画得不交叉”时会怎样
这是结构约束最明显的一章。
- 核心词：面、Euler 公式、对偶图、Kuratowski、Wagner。
- 作用：把组合问题和几何直观连接起来。
- 桥梁：第7章四色 / 五色问题直接建立在平面图上。
Chapter 7
图的着色：冲突消解与组合计数
全书最后一章把“结构”转成“分配”和“计数”。
- 边着色：资源分配给边；同色边构成匹配。
- 点着色：资源分配给点；同色点构成独立集。
- 色多项式：数合法着色方案有多少。
一句话总括
七章一句话
- 第1章：先学语言。
- 第2章：看最简单的连通图。
- 第3章：研究连通的强弱。
- 第4章：研究全局走法。
- 第5章：研究配对与分解。
- 第6章：研究嵌入与几何限制。
- 第7章：研究冲突着色与计数。
02
章与章之间到底怎么接：最容易断掉的连接点
七章依赖图（知识桥）
桥 1：第1章 → 第2章
树不是一个全新对象，而是把第1章的两个概念“连通 + 无圈”绑在一起。树的很多等价刻画，其实都在反复把“边数、连通、无圈、唯一简单路”互相转换。
桥 2：第2章 → 第3章
树是“最脆弱的连通图”：任一边都是割边，任一非叶可能成为割点。所以第3章研究连通度时，树常被拿来做极端例子。
桥 3：第3章 → 第4章
很多回路结论都要求一定连通性。比如 Hamilton 圈问题经常伴随 2-连通、较高最小度；而平面图中“每个面的边界是圈”也要求 2-连通。
桥 4：第4章 → 第5章
第4章里的 Hamilton 圈，本质上就是一个连通的 2-因子；第5章会系统化这个想法：1-因子 = 完美匹配，2-因子 = 若干圈的并。
桥 5：第5章 → 第7章
边着色最关键的一句话就是：同色边构成匹配。所以“最少几种边颜色”其实是在问“最少几个匹配能把所有边覆盖完”。这就是排课模型和 König 边着色定理的本质。
桥 6：第6章 → 第7章
地图着色看起来是“面着色”，但通过对偶图就变成了点着色。所以四色/五色问题并不是孤立内容，而是平面图 + 对偶图 + 顶点着色三者的汇合点。
03
全书反复出现的“母题”
母题 1：度数
- 第1章：度与度序列是最基础局部量。
- 第4章：Euler 图判定看顶点度奇偶。
- 第5章：正则图、k-因子、匹配相关上界都大量用度。
- 第6章：平面图边数上界推出 δ≤5。
- 第7章：χ′≥Δ、Vizing、χ≤Δ+1、Brooks，全都绕不开 Δ。
母题 2：圈
- 第2章：树 = 无圈连通图。
- 第4章：Euler / Hamilton 都是回路问题。
- 第5章：2-因子是若干圈的并。
- 第6章：平面图的面边界与圈紧密相关。
- 第7章：奇圈是二部性与 2-可着色的重要障碍。
母题 3：分解
- 第2章：生成树把复杂图简化成树。
- 第5章：匹配、1-因子、2-因子、森林分解最典型。
- 第7章：边着色等价于把边集分解成若干匹配。
母题 4：极值 + 构造
- “存在吗？”对应判定定理，例如 Hall、Tutte、Kuratowski。
- “最少 / 最多是多少？”对应极值量，如 χ、χ′、σ(G)。
- “怎么实际找出来？”对应算法或构造，如 Fleury、匈牙利、贪心着色、平面性算法。
你做题时最应该先识别的 5 个对象
点
点着色、连通度、割点。
边
边着色、割边、匹配。
路
树的唯一路、可扩路、Kempe 链。
圈
奇圈、Euler 圈、Hamilton 圈、面边界。
面
平面图、对偶、地图着色。
04
交叉对照：哪些结论虽然分属不同章节，但本质上是同一类思路
| 主题 | 章节 | 核心问题 | 本质 |
|---|---|---|---|
| 树 | 第2章 | 何为“最简连通图”？ | 用最少边保持连通 |
| 连通度 | 第3章 | 删去多少点/边会断开？ | 测图的稳健性 |
| Euler 图 | 第4章 | 能否一笔画遍所有边？ | 边的全局遍历 |
| Hamilton 图 | 第4章 | 能否经过每点恰一次成圈？ | 点的全局遍历 |
| 完美匹配 | 第5章 | 能否把所有点一一配对？ | 边的局部选择覆盖全图 |
| 1-因子 / 2-因子 | 第5章 | 能否把图拆成正则生成子图？ | 整体结构分解 |
| 平面性 | 第6章 | 能否无交叉嵌入平面？ | 结构受几何约束 |
| 点着色 | 第7章 | 最少几种颜色避免点冲突？ | 把顶点分组为独立集 |
| 边着色 | 第7章 | 最少几种颜色避免边冲突？ | 把边分组为匹配 |
| 色多项式 | 第7章 | 合法着色一共有多少种？ | 把存在性问题升级为计数问题 |
几个非常值得你刻意联想的“等价翻译”
边着色 = 把边分解成若干匹配。
点着色 = 把顶点分解成若干独立集。
Hamilton 圈 = 连通的 2-因子。
1-因子 = 完美匹配。
地图着色 = 对偶图的点着色。
树 = 连通 + 无圈 = 边数恰好 n−1 的极简连通图。
平面图判定 常靠反证：若平面，则必须满足 Euler 公式和边数上界。
05
如果你现在要总复习，推荐按这个顺序走
推荐复习顺序
第1章
基本语言→ 第2章
树的等价定义→ 第3章
κ, λ, 割点割边→ 第4章
Euler / Hamilton→ 第5章
匹配 / 因子→ 第6章
Euler 公式 / 平面性→ 第7章
χ, χ′, Pₖ(G)
基本语言→ 第2章
树的等价定义→ 第3章
κ, λ, 割点割边→ 第4章
Euler / Hamilton→ 第5章
匹配 / 因子→ 第6章
Euler 公式 / 平面性→ 第7章
χ, χ′, Pₖ(G)
为什么不建议直接从后面背公式？
因为第5–7章的大量结论都默认你已经能熟练识别：二部图、圈、奇偶性、连通性、正则性、补图。如果前面概念没连好，后面会感觉像很多孤立定理。
做题时的优先顺序
- 先看题目对象：点？边？路？圈？面？
- 再看目标：判定存在、求极值、还是计数？
- 最后才选工具：Euler/Hall/Tutte/Kuratowski/Brooks/Vizing/Pₖ(G)。
最容易混的三组概念
- Euler vs Hamilton：一个看边，一个看点。
- 点着色 vs 边着色：一个把点分成独立集，一个把边分成匹配。
- 完美匹配 vs 1-因子 vs 边着色色组：1-因子就是完美匹配；边着色的每个色组只是匹配，不一定完美。
06
一屏总记忆：最后真正需要留在脑子里的是什么
全书压缩版
第1章
学语言→ 第2章
学最简连通结构→ 第3章
学连通的强弱→ 第4章
学全局走法→ 第5章
学配对与分解→ 第6章
学平面限制→ 第7章
学冲突着色与计数
学语言→ 第2章
学最简连通结构→ 第3章
学连通的强弱→ 第4章
学全局走法→ 第5章
学配对与分解→ 第6章
学平面限制→ 第7章
学冲突着色与计数
全书 10 个最值得牢牢记住的连接句
- 树 = 连通 + 无圈。
- 树是最小连通图，因此每条边都很关键。
- Euler 图判定看顶点度的奇偶，Hamilton 图判定没有这么简洁。
- 1-因子就是完美匹配，2-因子就是若干圈。
- 边着色的每个色组都是匹配。
- 二部图里最大匹配、最小覆盖、边着色之间联系非常紧。
- 平面图的核心是 Euler 公式，不是“画得好看”。
- 地图着色通过对偶图变成点着色。
- χ(G) 问最少几色，Pₖ(G) 问总共有多少种合法 k 着色。
- 整本书的高频套路都是：找结构 → 套判定 → 做构造。
本汇总页基于你前面已经生成的七份章节复习 HTML（第1章到第7章）再次抽取主线，并专门强化“章节之间的连接关系”。如果你愿意，下一步我还可以继续给你做两种扩展版本：① 考前速记版（一页超浓缩）；② 思维导图版（更偏可视化，适合最后冲刺）。