第一篇 图及其算法 1
1.1 什么是图论 1
1.2 图的定义 7
1.3 Brouwer不动点定理 12
1.4 Dijkstra算法 14
习题一 17
1.5 树 22
1.6 生成树 26
1.6.1 生成树的个数 26
1.6.2 最优生成树的Kruskal算法 28
1.7 常用树 30
1.7.1 有序二元树 30
1.7.2 HuffmanA树 32
习题二 35
1.8 平面图 37
1.8.1 平面图及其Euler公式 37
1.8.2 对偶图和极大平面图 43
1.8.3 Kuratowsky定理 44
1.8.4 图的厚度 46
习题三 47
1.9 纵深搜索与平面嵌入算法 49
1.9.1 广度优先与深度优先搜索算法 49
1.9.2 求割顶和块的算法 52
1.9.3 有向图的DFS和极大强连通子图的算法 54
1.9.4 平面嵌入算法 56
习题四 63
1.10 匹配 64
1.10.1 匹配理论 65
1.10.2 二分图中最大匹配与最佳匹配的算法 72
习题五 76
1.11 图上遍历 78
1.11.1 Euler图 78
1.11.2 求Euler回路的算法 81
1.11.3 中国邮路问题 82
1.11.4 Harnilton图 84
习题六 91
1.12 色 92
1.12.1 边色数 93
1.12.2 顶色数与面色数 96
1.12.3 色多项式 99
习题七 103
1.13 支配集、独立集和Ramsey数 105
1.13.1 支配集和独立集 105
1.13.2 a（G），b（G），r（G）的计算 106
1.13.3 Ramsey数 110
1.13.4 多元Ramsey数和Schur定理 116
习题八 116
1.14 有向图 118
1.14.1 有向图的连通性 118
1.14.2 有向轨与竞赛图 119
1.14.3 有向圈与竞赛图 122
1.14.4 有向Euler图 125
习题九 129
1.15 网络流 130
1.15.1 Ford-Fulkerson最大流算法 130
1.15.2 Dinic最大流算法 133
1.15.3 有上下界的网络中的流 138
1.15.4 有供需约束的流 142
1.15.5 RERT问题 143
1.15.6 流与二分图 146
习题十 148
1.16 连通度 153
1.16.1 无向图的顶连通度 153
1.16.2 有向图的顶连通度 156
1.16.3 无向图的边连通度 157
1.16.4 有向图的边连通度和弱独立外向生成树 158
1.16.5 可靠通讯网络 160
习题十一 162
2.1 什么是组合论 166
第二篇 组合基础 166
2.2 鸽笼原理 169
2.3 ＋ ×原理与排列组合 172
2.3.1 无重复的排列组合 173
2.3.2 Catalan数 174
2.3.3 可重复的排列组合 178
习题一 182
2.4 容斥原理 184
习题二 192
2.5 生成函数 193
2.5.1 生成函数概念 193
2.5.2 组合数的生成函数 194
2.5.3 拆分自然数 196
2.5.4 排列数的生成函数 199
习题三 202
2.6 递归方程 204
2.6.1 递归方程的初值问题 204
2.6.2 线性常系数递归方程的生成函数解法 205
2.6.3 常系数线性齐次递归方程的特征值解法 208
2.6.4 常系数线性非齐次递归方程的解 212
2.6.5 递归方程的其它解法 212
2.6.6 Stirling数 215
习题四 216
第三篇 代数与计数 219
3.1 代数系统及其性质 219
3.1.1 代数系统的定义 219
3.1.2 代数系统的同构与同态 221
3.2 群、环、域 225
3.2.1 群 225
3.2.2 环 227
3.2.3 域 228
习题一 230
3.3.1 置换 233
3.3 置换群和循环群 233
3.3.2 置换群与循环群 237
3.4 Lagrange定理和Burnside定理 243
3.5 Polya定理 247
习题二 252
3.6 图的群 253
3.6.1 图的自同构群 253
3.6.2 有限群的Cayley图 259
习题三 264
4.1.1 圈空间 266
4.1 圈空间和断集空间 266
第四篇 离散数学中的空间,矩阵和拟阵 266
4.1.2 断集空间 269
4.2 关联矩阵和邻接矩阵 272
4.2.1 关联矩阵 272
4.2.2 邻接矩阵 279
4.3 圈矩阵和割集矩阵 286
4.4 开关网络分析 292
习题一 299
4.5.1 拟阵的概念 303
4.5 拟阵 303
4.5.2 拟阵理论 308
习题二 312
4.6 倒称矩阵与层次分析 314
4.7 正交拉丁方 322
4.8 区组设计与区组矩阵 327
4.8.1 BIBD问题 328
4.8.2 区组关联矩阵 328
4.8.3 Hadamard矩阵 331
4.8.4 区组设计的构作 333
4.9 魔矩阵密码 336
习题三 342
第五篇 不确定Turing机和计算的时间复杂度 344
5.1 好算法和坏算法 344
5.2 确定Turing机和NP类问题 346
5.3 NPC问题和Cook定理 350
5.4 NPC中的组合问题 356
5.5 NPC中的图论问题 360
习题 376
第六篇 数理逻辑 380
6.1.2 联结词与命题公式 381
6.1 命题逻辑 381
6.1.1 命题及其真假 381
6.1.3 真值表 382
6.1.4 等价公式、代换定理与对偶定理 385
6.1.5 范式 387
6.2 命题逻辑中的推理 390
6.2.1 蕴含关系 390
6.2.2 真值表推理法 391
6.2.3 直接推理法 392
习题一 393
6.2.4 间接推理法 393
6.3 谓词逻辑 395
6.3.1 命题的谓词表达形式 395
6.3.2 量词 396
6.3.3 谓词公式及其变元 397
6.3.4 谓词逻辑中的等价定律、代入规则 399
6.4 谓词逻辑中的推理 403
习题二 406
参考文献 409