图论与组合 · 已有部分内容
第 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 图、正则竞赛图、强连通、拓扑排序和有向欧拉图。
教材定位：中文教材第 1 章，§1.1-§1.4，pp.1-50；目录见 PDF 第 2 页。英文第二版对应第 1 章。