目录 1
第1章 组合问题与技术引论 1
1.1 工程时间问题 2
1.1.1 问题 2
1.1.2 分析 3
1.1.3 关键路径分析 5
1.1.4 一个建筑的例子 5
练习1.1 6
1.2 匹配问题 9
1.2.1 问题 9
1.2.2 分析 10
1.2.3 排列 11
1.2.4 航空公司问题的解决方案的实用性 12
练习1.2 13
1.3 背包问题 14
1.3.1 问题 14
1.3.2 分析 16
1.3.3 问题的再次考察 17
练习1.3 18
1.4 算法及其效率 19
1.4.1 算法的比较 19
1.4.2 多项式求值 20
1.4.3 子集生成算法 23
1.4.4 冒泡排序 25
练习1.4 27
历史注记 29
补充练习 30
计算机题 33
推荐读物 33
第2章 集合、关系和函数 35
2.1 集合运算 35
练习2.1 39
2.2 等价关系 40
练习2.2 44
2.3 同余关系 45
练习2.3 49
2.4 部分序关系 50
2.4.1 哈斯图 55
2.4.2 拓扑排序 56
练习2.4 58
2.5 函数 60
练习2.5 67
2.6 数学归纳法 69
练习2.6 74
2.7 应用 77
练习2.7 81
历史注记 84
补充练习 85
计算机题 89
推荐读物 89
3.1 图及其表示 91
第3章 图 91
3.1.1 图的其他表示 93
3.1.2 同构 94
练习3.1 97
3.2 通路和回路 100
3.2.1 欧拉回路和欧拉通路 103
3.2.2 哈密顿回路和通路 106
练习3.2 110
3.3 最短通路和距离 116
3.3.1 带权图 118
3.3.2 通路的数目 122
练习3.3 123
3.4 图着色 126
练习3.4 131
3.5 有向图和有向多重图 134
3.5.1 有向图的表示 135
3.5.2 有向多重图 136
3.5.3 有向欧拉回路和通路 139
3.5.4 有向哈密顿回路和通路 140
练习3.5 142
历史注记 149
补充练习 150
计算机题 155
推荐读物 156
4.1 树的性质 157
第4章 树 157
练习4.1 162
4.2 生成树 165
4.2.1 广度优先搜索 167
4.2.2 最小生成树和最大生成树 169
4.2.3 普里姆算法的证明 173
练习4.2 174
4.3 深度优先搜索 179
回溯 184
练习4.3 186
4.4 根树 189
练习4.4 194
4.5.1 表达式树 197
4.5 二叉树和遍历 197
4.5.2 前序遍历 199
4.5.3 后序遍历 201
4.5.4 中序遍历 203
练习4.5 205
4.6 最优二叉树和二叉搜索树 207
4.6.1 最优二叉树 207
4.6.2 二叉搜索树 214
练习4.6 219
历史注记 224
补充练习 225
计算机题 228
推荐读物 229
5.1 相异代表系 230
第5章 匹配 230
练习5.1 233
5.2 图中的匹配 235
5.2.1 偶图的矩阵 237
5.2.2 覆盖 238
练习5.2 240
5.3 匹配算法 242
5.3.1 运用算法于最大独立集 245
5.3.2 分配课程 247
练习5.3 249
5.4 算法的应用 252
5.4.1 考尼格定理 253
5.4.2 霍尔定理的证明 254
5.4.3 瓶颈问题 256
练习5.4 257
5.5 匈牙利方法 259
练习5.5 265
历史注记 266
补充练习 267
计算机题 269
推荐读物 270
第6章 网络流 271
6.1 流和割 271
练习6.1 278
6.2 流增广算法 280
练习6.2 287
6.3 最大流最小割定理 290
练习6.3 294
6.4 流和匹配 296
练习6.4 300
历史注记 303
补充练习 304
计算机题 307
推荐读物 308
第7章 计数技术 309
7.1 帕斯卡三角形和二项式定理 309
练习7.1 312
7.2 三个基本原理 313
练习7.2 317
7.3 排列和组合 320
练习7.3 323
7.4 允许重复的排列和组合 324
练习7.4 328
7.5 概率 330
练习7.5 333
＊7.6 容斥原理 335
练习7.6 341
＊7.7 排列和r-组合的生成 344
练习7.7 349
历史注记 350
补充练习 351
计算机题 354
推荐读物 355
第8章 递推关系与生成函数 356
8.1 递推关系 356
练习8.1 363
8.2 迭代法 365
练习8.2 372
8.3 常系数线性差分方程 374
练习8.3 381
＊8.4 用递推关系分析算法的效率 383
8.4.1 分而治之算法 385
8.4.2 排序算法的效率 391
练习8.4 391
8.5 用生成函数计数 393
8.5.1 生成函数 394
8.5.2 形式幂级数 395
练习8.5 398
8.6 生成函数的代数 399
练习8.6 406
历史注记 407
补充练习 408
计算机题 412
推荐读物 412
第9章 组合电路和有限状态机 413
9.1 逻辑门 413
练习9.1 419
9.2 构造组合电路 422
练习9.2 426
9.3 卡诺图 429
练习9.3 438
9.4 有限状态机 441
9.4.1 奇偶校验机 442
9.4.2 带输出的有限状态机 444
练习9.4 446
历史注记 449
补充练习 450
计算机题 452
推荐读物 453
附录A 逻辑和证明简介 454
A.1 命题和联结词 454
练习A.1 460
A.2 逻辑等价 461
练习A.2 464
A.3 证明的方法 465
练习A.3 469
历史注记 470
补充练习 471
推荐读物 473
附录B 矩阵 474
历史注记 479
附录C 本书中的算法 481
附录D 各章奇数练习题答案 486
参考书目 531
历史注记的参考书目 535