第1章 引言 1
1.1 图与图模型 1
1.2 连通图 8
1.3 若干常见的图类 17
1.4 多重图与有向图 24
第2章 度 27
2.1 顶点的度 27
2.2 正则图 33
2.3 度序列 37
2.4 延伸阅读:图与矩阵 41
2.5 专题探索:不规则图 44
第3章 同构图 48
3.1 同构的定义 48
3.2 同构关系 55
3.3 延伸阅读:图与群 57
3.4 延伸阅读:重构与可解性 67
第4章 树 74
4.1 割边 74
4.2 树 76
4.3 最小生成树问题 81
4.4 延伸阅读:生成树的个数 87
第5章 连通性 93
5.1 割点 93
5.2 块 96
5.3 连通度 99
5.4 Menger定理 108
5.5 专题探索:测地集 113
第6章 可遍历性 116
6.1 Euler图 116
6.2 Hamilton图 122
6.3 专题探索:Hamilton链与Hamilton数 133
6.4 延伸阅读:早期的图论书籍 137
第7章 有向图 141
7.1 强有向图 141
7.2 竞赛图 148
7.3 延伸阅读:决策 154
7.4 专题探索:酒瓶问题 158
第8章 匹配与分解 161
8.1 匹配 161
8.2 因子分解 170
8.3 分解与优美标号 184
8.4 延伸阅读:立即疯游戏 189
8.5 延伸阅读:Petersen图 194
8.6 专题探索:图的γ标号 198
第9章 可平面性 201
9.1 平面图 201
9.2 图嵌入到曲面 213
9.3 延伸阅读:图的子式 221
9.4 专题探索:图嵌入到图 224
第10章 染色 229
10.1 四色问题 229
10.2 顶点染色 236
10.3 边染色 248
10.4 延伸阅读:Heawood地图染色定理 255
10.5 专题探索:局部染色 259
第11章 Ramsey数 264
11.1 图的Ramsey数 264
11.2 Turán定理 273
11.3 专题探索:彩色Ramsey数 279
11.4 延伸阅读:Erd?s数 285
第12章 距离 290
12.1 图的中心 290
12.2 远点 295
12.3 延伸阅读:定位数 302
12.4 延伸阅读:绕路距离和有向距离 306
12.5 专题探索:频道分配 311
12.6 专题探索:图与图之间的距离 316
第13章 控制 319
13.1 图的控制数 319
13.2 专题探索:分层 329
13.3 专题探索:关灯游戏 334
13.4 延伸阅读:明天更美好 337
附录1 集合与逻辑 339
附录2 等价关系与映射 343
附录3 证明方法 347
奇数号习题的解答与提示 353
参考文献 380
人名索引 388
数学术语索引 391
符号列表 398