本书充分考虑到初学者的需要，内容、例题、习题都经过精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。本书注重算法，且算法描述独立于某种具体的编程语言。教师可根据学生的层次和兴趣来灵活拓展和组织讲解内容。
如今，数学的应用越来越多地涉及离散而非连续的模型，其主要原因是现代社会越来越多地用到计算机。本书适用于一学期的离散数学入门课程。
预备知识
虽然按照本书讲授的课程只要求很少的数学预备知识，但还是要求学生至少达到修读过两年高中数学所应具有的水平，包括解题和运算的技能以及抽象思维的能力。
方法
本书强调算法并以此贯穿全书。算法用文字表述，不需要具体编程语言的知识。
主题的选择
本书主题的选择基于多个专业组织的建议，包括MAA（美国数学协会）一年级和二年级离散数学课程制定工作组的建议、NCTM（National Council of Teachers of Mathematics，美国数学教师理事会）的“学校数学教育的原则与标准”和CBMS（Conference Board of the Mathematical Sciences，美国数学科学联合会）对数学教学的建议等。
灵活性
虽然本书是针对一学期的课程设计的，但是本书所包含的材料多于一个学期所能覆盖的内容。因此，教师可以根据学生的特定需求和兴趣方便地选择主题。本书以前的版本在从计算机科学专业的一年级课程到数学专业的高年级课程等许多课程中用过，并得到了良好的反映。现在的这个版本仍然为教师提供了灵活性，以适用于各种不同专业学生的课程。
第5版的变动
第5版的主要变动是新增了一章—第3章，讨论同余、欧几里得算法及相关的数论方面的内容、RSA公钥密码技术、检错码和纠错码（包括矩阵码）。本书其余内容与这一章不相关，所以可由教师根据需要进行取舍。学习矩阵码的内容要求熟悉矩阵，所以在学习编码理论这一章之前，不熟悉矩阵的学生需要先阅读附录B。（详见下面的“章节独立性”和“课程设置建议”。）
另外，新版本在表述的清晰性方面有所改进，对离散数学的新进展也给予了关注。
习题
本书的习题安排错落有致，灵活性强。每节后都有大量简单的计算题和算法题，其中大多数习题有助于学生针对离散数学的概念和算法进行全面练习，这对数学基础较弱的学生尤其重要；另一些习题拓展了正文中的材料，或者引入了正文中未论述过的新概念。带*号的习题是更具挑战性的问题。教师应根据课程和学生水平从中挑选。奇数号计算题的答案附在本书末尾。在每一章的末尾，有一组补充习题，用来温习各章最重要的概念和技术，以及探讨正文中未讨论的新概念。
章节独立性
在采用本书进行教学时，各章的顺序可以灵活地安排。下图显示了各章的依赖关系。其中，虚线表示第6章仅与第4章的前几节内容相关。本书只假定读者具有高中几何课程对于逻辑与证明的熟练程度，而对那些偏好更形式化处理的读者提供了一个附录（附录A），可以将它作为独立的单元在任何时候讲授，也可以与第9章一起讲授。仅在3.5～3.6节和第4章讨论邻接矩阵时，要求熟悉矩阵（附录B）。
第1章和第2章实质上是导论。第1章给出本书所处理的离散问题的样例，应很快讲授完。该章只是提出某些问题，而在本书的后面才给出解答。1.4节包含对复杂性的讨论，可以略过它，或者推迟到学生有更多算法经验时再讲授。在这一节中，教师可以只讲解与学生关系最密切的示例算法。
第2章复习各种基本主题，包括集合、关系、函数和数学归纳法。该章可以讲授得稍快些，这取决于学生的数学背景和课程的层次。对于数学背景较好的学生，第2章的很多内容应该可以让他们自学。如上图所示，除了第5章和第7章依赖于第4章，以及第6章与第4章前几节的内容相关外，其余各章均彼此独立。
为配合新的第3章，同余的内容从第2章中移出。与第4版一样，这个内容（见第5版的3.1节）可以在讲完2.2节（等价关系）以后的任何时候学习。
课程设置建议
下面的表格给出了三个课程设置范例。课程A的重点是图论及其应用，涵盖了第4～7章的大部分内容。课程B涉及图论较少，更强调计数技术。课程C的重点是计算机科学专业的学生所感兴趣的论题。
课程A课程B课程C
章课时数章课时数章课时数
141（跳过1.4节）314
252525
4646附录B1
575636
668846
749556
88附录A395
94附录A3
104
本书适用于各种层次的“离散数学”课程。比如，计算复杂性是一个很重要的主题，本书对许多算法的复杂性给予了关注。但是，这是一个较难的主题，其论述深度应当与课程的层次和学生的基础相吻合。
计算机题
各章结尾均给出一组计算机题，这些计算机题与该章的内容、算法等相关。本书刻意用普通的术语来叙述计算机题，以便适应使用各种计算系统和语言的学生。
致谢
我们衷心地感谢下列审阅本书的数学家：米勒斯维尔大学的Dorothee Blum、威斯康星大学麦迪逊分校的Richard Brualdi、佛罗里达州立大学的John L. Bryant、波特兰州立大学的 Richard Crittenden、乔治梅森大学的Klaus Fischer、东得克萨斯州立大学的Dennis Grantham、Clemson大学的William R. Hare、东密歇根大学的Christopher Hee、佛罗里达大西洋大学的Frederick Hoffman、佛罗里达国际大学的Julian L. Hook、Broome社区学院的Carmelita Keyes、 Macalester学院的Richard K. Molnar、普度大学Calumet分校的Catherine Murphy、佛罗里达大学的Charl
出版者的话
译者序
前言
致学生
离散数学纪年表
第1章 组合问题与组合技术引论1
1.1 工程完成时间的问题1
1.1.1 问题1
1.1.2 分析2
1.1.3 关键路径分析3
1.1.4 一个建筑的例子4
1.2 匹配问题7
1.2.1 问题7
1.2.2 分析7
1.2.3 排列8
1.2.4 航空公司问题解决方案的实用性9
1.3 背包问题11
1.3.1 问题11
1.3.2 分析12
1.3.3 回顾实验问题14
1.4 算法及其效率15
1.4.1 算法的比较15
1.4.2 多项式求值16
1.4.3 子集生成算法19
1.4.4 冒泡排序21
历史注记24
补充习题25
计算机题27
推荐读物27
第2章 集合、关系和函数28
2.1 集合运算28
2.2 等价关系32
*2.3 偏序关系37
2.3.1 偏序和全序37
2.3.2 哈斯图40
2.3.3 拓扑排序41
2.4 函数44
2.5 数学归纳法52
2.6 应用58
历史注记65
补充习题66
计算机题69
推荐读物69
第3章 编码理论70
3.1 同余70
3.2 欧几里得算法75
3.2.1 最大公约数75
3.2.2 欧几里得算法75
3.2.3 欧几里得算法的效率77
3.2.4 扩展的欧几里得算法77
3.3 RSA方法79
3.3.1 指数取模80
3.3.2 RSA方法的解密83
3.3.3 RSA方法的可行性85
3.4 检错码和纠错码86
3.5 矩阵码93
3.5.1 矩阵码93
3.5.2 编码的校验矩阵94
3.6 单纠错矩阵码99
3.6.1 校验矩阵行译码法100
3.6.2 汉明码101
历史注记105
补充习题106
计算机题109
推荐读物109
第4章 图110
4.1 图及其表示110
4.1.1 图的概念和表示110
4.1.2 图的其他表示112
4.1.3 同构113
4.2 通路和回路117
4.2.1 多重图、通路和回路117
4.2.2 欧拉回路和欧拉通路119
4.2.3 哈密顿回路和哈密顿通路122
4.3 最短通路和距离129
4.3.1 广度优先搜索算法129
4.3.2 带权图131
4.3.3 通路的数目134
4.4 图着色138
4.5 有向图和有向多重图144
4.5.1 有向图145
4.5.2 有向图的表示145
4.5.3 有向多重图146
4.5.4 有向欧拉回路和有向欧拉通路148
4.5.5 有向哈密顿回路和有向哈密顿通路149
历史注记155
补充习题156
计算机题160
推荐读物161
第5章 树162
5.1 树的性质162
5.2 生成树168
5.2.1 生成树169
5.2.2 广度优先搜索法169
5.2.3 最小生成树和最大生成树171
5.2.4 普里姆算法的证明174
5.3 深度优先搜索179
5.3.1 深度优先搜索法179
5.3.2 回溯183
5.4 根树188
5.5 二叉树和遍历193
5.5.1 表达式树193
5.5.2 前序遍历195
5.5.3 后序遍历197
5.5.4 中序遍历199
5.6 最优二叉树和二叉搜索树202
5.6.1 最优二叉树202
5.6.2 二叉搜索树208
历史注记215
补充习题216
计算机题219
推荐读物220
第6章 匹配221
6.1 相异代表系221
6.1.1 相异代表系221
6.1.2 霍尔定理222
6.2 图中的匹配225
6.2.1 匹配225
6.2.2 偶图的矩阵227
6.2.3 覆盖227
6.3 匹配算法231
6.3.1 独立集算法的应用示例231
6.3.2 将算法运用于最大独立集233
6.3.3 独立集算法234
6.3.4 课程分配235
6.4 算法的应用239
6.4.1 柯尼希定理240
6.4.2 霍尔定理的证明241
6.4.3 瓶颈问题242
6.5 匈牙利方法245
6.5.1 匈牙利算法245
6.5.2 匈牙利算法的证明247
6.5.3 不是方阵的矩阵248
6.5.4 最大和独立集249
历史注记250
补充习题251
计算机题252
推荐读物253
第7章 网络流254
7.1 流和割254
7.2 流增广算法261
7.3 最大流最小割定理269
7.4 流和匹配274
历史注记280
补充习题280
计算机题283
推荐读物283
第8章 计数技术284
8.1 帕斯卡三角形和二项式定理284
8.2 3个基本原理287
8.3 排列和组合293
8.4 允许重复的排列和组合297
8.5 概率302
*8.6 容斥原理306
*8.7 排列和r组合的生成315
8.7.1 排列的词典序枚举315
8.7.2 r组合的词典序枚举317
历史注记320
补充习题321
计算机题323
推荐读物324
第9章 递推关系与生成函数325
9.1 递推关系325
9.2 迭代法333
9.3 常系数线性差分方程341
9.3.1 一阶常系数线性差分方程341
9.3.2 二阶线性齐次差分方程344
*9.4 用递推关系分析算法的效率350
9.4.1 顺序查找算法和冒泡排序算法的效率…350
9.4.2 分治算法的效率352
9.4.3 排序算法的效率357
9.5 用生成函数计数359
9.5.1 生成函数360
9.5.2 形式幂级数361
9.6 生成函数的代数365
历史注记372
补充习题373
计算机题375
推荐读物376
第10章 组合电路和有限状态机377
10.1 逻辑门377
10.2 构造组合电路383
10.3 卡诺图388
10.4 有限状态机397
10.4.1 奇偶校验机398
10.4.2 有限状态机399
10.4.3 带输出的有限状态机400
历史注记404
补充习题405
计算机题407
推荐读物408
附录A 逻辑和证明简介409
附录B 矩阵425
附录C 本书中的算法432
参考文献436
奇数号习题答案440
书单推荐
