第1章 基本概念 1
1.1 什么是图 1
定义 1
图模型 2
矩阵和同构 4
分解和特殊图 7
习题 10
1.2 路径、环和迹 13
图的连通性 14
二部图 17
欧拉回路 19
习题 22
1.3 顶点度和计数 25
计数和双射 26
极值问题 28
图序列 32
习题 35
1.4 有向图 40
定义和例子 40
顶点度 44
欧拉有向图 45
定向和竞赛图 46
习题 47
第2章 树和距离 51
2.1 基本性质 51
树的性质 51
树和图中的距离 54
不相交生成树（选学） 56
习题 57
2.2 生成树和枚举 63
树的枚举 63
图的生成树 65
分解和优美标记 67
分叉和欧拉有向图（选学） 69
习题 71
2.3 最优化和树 74
最小生成树 74
最短路径 76
计算机科学中的树（选学） 78
习题 80
第3章 匹配和因子 84
3.1 匹配和覆盖 84
最大匹配 84
Hall匹配条件 86
最小－最大定理 87
独立集和覆盖 88
支配集（选学） 90
习题 92
3.2 算法和应用 96
最大二部匹配 96
加权二部匹配 98
稳定匹配（选学） 102
快速二部匹配（选学） 103
习题 105
3.3 一般图中的匹配 106
Tutte1-因子定理 107
图的f-因子（选学） 110
Edmonds开花算法（选学） 110
习题 113
第4章 连通度和路径 117
4.1 割和连通度 117
连通度 117
边－连通度 118
块 121
习题 123
2－连通图 126
4.2 k－连通图 126
有向图的连通度 129
k－连通图和k－边连通图 130
Menger定理的应用 133
习题 135
4.3 网络流问题 138
最大网络流 138
整数流 142
供应和需求（选学） 144
习题 147
定义和实例 151
5.1 顶点着色和上界 151
第5章 图的着色 151
上界 153
Brooks定理 156
习题 157
5.2 k－色图的结构 162
大色数图 163
极值问题和Turan定理 164
颜色－临界图 167
强制细分 169
习题 171
真着色的计数 175
5.3 计数方面的问题 175
弦图 179
完美图点滴 181
无环定向的计数（选学） 182
习题 183
第6章 可平面图 186
6.1 嵌入和欧拉公式 186
平面作图 186
对偶图 188
欧拉公式 191
习题 193
6.2 可平面图的特征 195
Kuratowski定理的预备知识 196
凸嵌入 197
可平面性测试（选学） 200
习题 202
6.3 可平面性的参数 204
可平面图的着色 204
交叉数 208
具有更高亏格的表面（选学） 212
习题 214
边着色 218
第7章 边和环 218
7.1 线图和边着色 218
线图的特征（选学） 223
习题 225
7.2 哈密顿环 229
必要条件 229
充分条件 230
有向图中的环（选学） 234
习题 235
7.3 可平面性、着色和环 240
Tait定理 240
Grinberg定理 242
鲨鱼图（选学） 243
流和环覆盖（选学） 245
习题 251
第8章 其他主题（选学） 255
8.1 完美图 255
完美图定理 256
弦图的再研究 258
其他类型的完美图 261
非完美图 266
强完美图猜想 271
习题 274
8.2 拟阵 278
遗传系统和示例 278
拟阵的性质 282
生成函数 285
拟阵的对偶性 287
拟阵的子式和可平面图 288
拟阵的交 291
拟阵的并 293
习题 296
鸽巢原理的再研究 301
8.3 Ramsey理论 301
Ramsey定理 303
Ramsey数 306
关于图的Ramsey理论 308
Sperner引理和带宽 309
习题 312
8.4 其他极值问题 316
图的编码 317
分叉和流言 323
序列着色和可选择性 326
使用路径和环的划分 329
周长 332
习题 337
8.5 随机图 339
存在性和期望值 340
几乎所有图均具有的性质 343
阈值函数 345
演变和图参数 348
连通度、团和着色 350
鞅 353
习题 358
8.6 图的特征值 362
特征多项式 362
实对称矩阵的线性代数 365
特征值和图参数 367
正则图的特征值 368
特征值和扩张图 371
强正则图 372
习题 374
附录A 数学基础 378
附录B 最优化和复杂度 394
附录C 部分习题的提示 405
附录D 术语表 412
附录E 补充阅读材料 439
附录F 参考文献 443