课程总纲 · 8 个单元 · 28 个知识点
图论与组合
从图的结构、路径与计数出发，学习树、匹配、连通与网络流，再进入着色、可平面图和组合专题。
章节与知识点
按 West《图论导引（原书第2版）》的 8 章 28 节组织，参照英文第二版目录与第 4 章课堂讲义。第 8 章为教材选学内容；教材目录用于呈现知识脉络，不等同于课堂进度或考试范围。
-
第 1 章 基本概念
已有部分内容建立图、同构和连通的语言，用度数、双射与极值思想处理计数，并学习有向图。
中文教材第 1 章，§1.1-§1.4，pp.1-50；目录见 PDF 第 2 页。英文第二版对应第 1 章。
- 1.1 什么是图
中文教材 p.1 起。认识图模型、矩阵表示、同构、分解与特殊图。
- 1.2 路径、环和迹
中文教材 p.13 起。区分路径、环与迹，联系连通性、二部图和欧拉回路。
- 1.3 顶点度和计数
中文教材 p.25 起。通过度数和双射计数，进入极值问题与图序列。
- 1.4 有向图
中文教材 p.40 起。学习入度、出度、有向欧拉图、定向与竞赛图。
- 作业1.2 连通、迹与欧拉图
对应 §1.2；含连通与邻接辨析、闭合迹分解、排列图及欧拉图习题。
- 作业1.3 度数、环计数与极值
对应 §1.3；含奇度点、三角形计数、最大二部子图、完全图中的环和边数极值。
- 作业1.4 有向图与 de Bruijn 图
对应 §1.4；含 de Bruijn 图、正则竞赛图、强连通、拓扑排序和有向欧拉图。
-
第 2 章 树和距离
已有部分内容由树的结构与距离进入生成树计数，再讨论最小生成树和最短路径。
中文教材第 2 章，§2.1-§2.3，pp.51-83；目录见 PDF 第 2 页。英文第二版对应第 2 章。
- 2.1 基本性质
中文教材 p.51 起。学习树的性质、树和图中的距离，以及不相交生成树这一选学方向。
中文教材 p.63 起。学习树的枚举与生成树计数；阅读笔记以 Prüfer 序列、Cayley 公式和矩阵树定理为主。
- 2.3 最优化和树
中文教材 p.74 起。区分最小生成树与最短路径的优化目标，理解树在算法中的作用。
- 拓展阅读单点度约束生成树：问题定义与比较示例
§2.3 的延伸建模阅读，非教材节次；通过一个有限例子区分度数约束、可行性与最大边优先的词典序目标。
-
第 3 章 匹配和因子
章节框架从匹配与覆盖的关系进入二部图算法，再研究一般图中的完美匹配和因子。
中文教材第 3 章，§3.1-§3.3，pp.84-116；目录见 PDF 第 2 页。英文第二版对应第 3 章。
- 3.1 匹配和覆盖
中文教材 p.84 起。联系最大匹配、Hall 条件、最小最大定理、独立集与覆盖。
- 3.2 算法和应用
中文教材 p.96 起。学习最大二部匹配与加权二部匹配，了解稳定匹配和快速算法的选学内容。
- 3.3 一般图中的匹配
中文教材 p.106 起。以 Tutte 的 1-因子定理为主线，进一步认识 f-因子与开花算法。
-
第 4 章 连通度和路径
已有部分内容从点割、边割与块的结构，推进到不相交路径，再把连通问题与网络流联系起来。
中文教材第 4 章，§4.1-§4.3，pp.117-150；目录见 PDF 第 2-3 页。教师 Chapter 4 讲义的三个部分与本章三节对应。
- 4.1 割和连通度
中文教材 p.117 起。比较点连通度、边连通度和块，理解删除顶点或边对连通性的影响。
- 4.2 k-连通图
中文教材 p.126 起。学习 2-连通、有向图连通性、k-连通与 Menger 定理的应用。
- 4.3 网络流问题
中文教材 p.138 起。讨论最大网络流、整数流，以及供给和需求的选学模型。
- 笔记点连通度与 Harary 图
对应 §4.1 的点连通部分：点割、连通度、完全图与超立方体例子及 Harary 图。
- 教师讲义Connectivity and Paths
Hengjia Wei，Chapter_4___Connectivity_and_Paths.pdf；割与连通 PDF pp.3-32，k-连通图 pp.33-83，网络流 pp.84-124。
-
第 5 章 图的着色
章节框架研究顶点着色与色数界，连接临界结构、极值图和着色计数。
中文教材第 5 章，§5.1-§5.3，pp.151-185；目录见 PDF 第 3 页。英文第二版对应第 5 章。
- 5.1 顶点着色和上界
中文教材 p.151 起。从着色的定义与例子进入上界和 Brooks 定理。
- 5.2 k-色图的结构
中文教材 p.162 起。学习大色数图、Turán 极值问题、颜色临界图和强制细分。
- 5.3 计数方面的问题
中文教材 p.175 起。研究正常着色的计数，联系弦图、完美图与无环定向。
-
第 6 章 可平面图
章节框架学习平面嵌入及其结构限制，借助欧拉公式、对偶与可平面性参数研究图。
中文教材第 6 章，§6.1-§6.3，pp.186-217；目录见 PDF 第 3 页。英文第二版对应第 6 章。
- 6.1 嵌入和欧拉公式
中文教材 p.186 起。区分图与平面画法，认识对偶图和欧拉公式。
- 6.2 可平面图的特征
中文教材 p.195 起。学习 Kuratowski 定理的相关结构、凸嵌入及可平面性测试。
- 6.3 可平面性的参数
中文教材 p.204 起。讨论可平面图着色、交叉数，以及更高亏格曲面的选学内容。
-
第 7 章 边和环
章节框架把着色问题转向边，研究哈密顿环，并联系可平面性、着色与环结构。
中文教材第 7 章，§7.1-§7.3，pp.218-254；目录见 PDF 第 3 页。英文第二版对应第 7 章。
- 7.1 线图和边着色
中文教材 p.218 起。通过线图联系边与顶点的着色问题。
- 7.2 哈密顿环
中文教材 p.229 起。区分遍历顶点与遍历边，研究哈密顿环存在的必要条件与充分条件。
- 7.3 可平面性、着色和环
中文教材 p.240 起。学习 Tait 与 Grinberg 定理，了解流和环覆盖等选学方向。
-
第 8 章 其他主题（选学）
章节框架从完美图、拟阵和 Ramsey 理论，拓展到极值、随机与谱方法。
中文教材第 8 章，§8.1-§8.6，pp.255-377；目录见 PDF 第 3-4 页，整章标为选学。英文第二版对应 Additional Topics (optional)。
- 8.1 完美图
中文教材 p.255 起。考察完美图、弦图及相关图类的结构。
- 8.2 拟阵
中文教材 p.278 起。从遗传系统和例子进入拟阵性质、对偶、交与并。
- 8.3 Ramsey 理论
中文教材 p.301 起。由鸽巢原理进入 Ramsey 定理、Ramsey 数及图上的组合问题。
- 8.4 其他极值问题
中文教材 p.316 起。考察图的编码、分叉、列表着色以及用路径和环进行划分。
- 8.5 随机图
中文教材 p.339 起。通过存在性、期望与阈值研究随机图的性质和演变。
- 8.6 图的特征值
中文教材 p.362 起。联系特征多项式、实对称矩阵与图参数，认识正则图和扩张图。