离散数学(第4版)/国外经典教材.计算机科学与技术

本书是离散数学的入门教材，充分考虑到了初学者的需要，内容、例题、习题都作了精心的挑选和组织，讲解细致，叙述浅显易懂，循序渐进，用例贴近日常生活或计算机应用，并注重算法。主要内容包括集合、关系、函数、图论、组合数学、组合电路设计、有限自动机、算法、逻辑等。 本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书。

前 言 如今数学的应用越来越多地涉及到离散而非连续的模型，造成这种趋势的主要原因是现代社会与计算机日益密切的融合。本书适用于大学第一学期的离散数学入门课程。 1．预备知识 虽然按照本书讲授的课程只要求很少的数学预备知识，但还是要求学生具备修读过至少两年高中数学所应具有的数学水平，包括解题和算法的技能以及抽象思维的能力。 2．途径 本书强调算法并以此贯穿全书。算法用英语表述，不需要具体编程语言的知识。 3．主题的选择 本书的主题选择基于多个专业组织的建议，包括MAA（美国数学协会）关于一年级和二年级离散数学工作组的建议、NCTM（National Council of Teachers of Mathematics，美国数学教师协会）的《学校数学的原则与标准》和CBMS（Conference Board of the Mathematical Sciences，美国数学科学联合会）对教师的数学教育的建议等。 4．灵活性 虽然本书是针对大学第一学期的课程设计的，但是本书所包含的材料多于一个学期或者两个学期所能覆盖的内容。因此，教师可以方便地选择主题以适应学生的特定需求和兴趣。本书以前版本的使用者在许多课程中都反映取得了很大的成功，从计算机科学专业的一年级课程，到数学专业的高年级课程。现在的这个版本仍然为教师提供了灵活性，以设计适宜于各种不同类型学生的课程。 5．第4版的变动 根据第3版使用者的建议，在每章的末尾增加了历史评注。此外，重写了第3章和第4章，以使广度优先算法的地位更突出（现在它出现在3.3节，并应用于3.4节和4.2节）。第3章和第4章的许多例子也重写了，以方便这样的教师，他们不希望讨论算法的形式化表述细节。这些例子现在写在算法的前面，能够更好地揭示算法是如何工作的，而不必讨论形式化的算法本身。以前分开的关于生成树以及极小和极大生成树的章节现在合并在新的4.2节中。关于矩阵的介绍性材料从第3章移出，放到新的附录B中。另一个新的附录（附录C）描述了本书算法中使用的循环与分支结构。全书中的讲解也有不少改变，以增加写作上的清晰性。 6．习题 本书的习题配置得很有适应性。大量简单的计算题和算法题包括在每一节的末尾，这些习题为学生提供了对离散数学的概念和算法的全面练习，对数学背景较弱的学生尤其重要。另一些习题拓展了正文中的材料，或者引进了正文中未论述过的新概念。带*号的习题表示更具挑战性的问题。教师应挑选适合学生的课程和习题。奇数序号的练习题的答案附在本书末尾。在每一章的末尾，有一组补充题，用于温习各章最重要的概念和技术，以及探讨未被正文覆盖的新概念。 7．各章的独立性 在采用本书进行教学时，各章的顺序可以灵活地安排。下图说明了各章的依赖关系。其中的虚线表示第5章仅需要第3章的最初几节。虽然本书只假定读者具有高中几何课程的对逻辑与证明的熟练程度，但是本书为那些偏好更形式化处理的人提供了一个附录（附录A）。如果要讲授这个附录，可以将它作为独立的单元在任何时候讲授，也可以与第9章一起联合讲授。 第1章和第2章本质上是导论。第1章给出本课程所处理的离散问题的样例，应很快讲授完。有些问题提出来了，但是在本书的后面才给出解答。1.4节包含对复杂性的讨论，可以略过它，或者推迟到学生有更多算法经验时再讲授。在这一节中，教师可以只讲解与学生关联最密切的示例算法。 第2章复习各种基本主题，包括集合、关系、函数和数学归纳法。本章可以讲授得稍快，这取决于学生的数学背景和课程的层次。对于数学背景较好的学生，第2章的很多内容可以让他们自行阅读。如上图所示，除了第4章和第6章依赖于第3章，以及第5章需要第3章开头的概念外，其余各章均彼此独立。 8．其他可能的课程 强调图论及其应用的课程可讲授第3～6章的大部分，而涉及图论较少的课程则可以略去第5章和第6章，并专注于第7～9章。遵循这些线路的两个课程的范例如下表所示。 课 程 甲 课 程 乙 章 节 课 时 数 章 节 课 时 数 1 4 1（跳过1.4节） 3 2 6 2 6 续表 课 程 甲 课 程 乙 章 节 课 时 数 章 节 课 时 数 3 6 3 6 4 7 4 6 5 6 7 8 6 4 8 5 7 8 附录 3 9 4 采用本书可以讲授各种程度的高级课程。比如，计算复杂性是一个很重要的主题，本书对许多算法的复杂性给予了关注。但是，这是一个较难的主题，对其论述深度应当与课程的层次和学生的基础相吻合。 9．计算机题 每章以一组计算机题结束，这些计算机题与该章的内容、算法等相关。这些计算机题被刻意地用普通的术语来叙述，以便适应使用各种计算系统和语言的学生。 10．补充读物 Student’s Solution Manual可供学生购买，其中提供了奇数序号习题的详细但未必是最佳的解答，可用书号EISBN 0-201-75483-5订购。Instructor’s Answer Manual也已备妥，其中包含所有偶数序号的计算题的解答，书号是EISBN 0-201-75482-7。 11．致谢 我们衷心地感谢下列数学家，他们的评论指引了本书的写作。他们是Millersville大学的Dorothee Blum、Wisconsin大学Madison分校的Richard Brualdi、Florida州立大学的John L. Bryant、Portland州立大学的 Richard Crittenden、George Mason大学的Klaus Fischer、东Texas州立大学的Dennis Grantham、Clemson大学的William R. Hare、 西Michigan大学的Christopher Hee、 Florida Atlantic大学的Frederick Hoffman、 Florida国际大学的Julian L. Hook、Broome公立学院的Camlelita Keyes、 Macalester学院的Richard K. Molnar、 Purdue大学Calumel分校的 Catherine Murphy、 Florida大学的Charles Nelson、 Miami大学的Fred Schuurmann、 Charles S. Mott公立学院的Karen Sharp和新Hampshire大学的Donovan H.Van Osdol。为本书第二版的改进提供了有益意见的有我们的同事Saad El-Zanati、Michael Plantholt和Shailesh Tipnis，以及全美国各地本书的使用者，还有Bemidji州立大学的Elaine Bohanon、Evergreen州立学院的George Dimitroff、Wisconsin-Whitewater大学的Richard Enstad、 西Michigan大学的Donald Goldsmith、Kentucky教育网络的Thomas R. Graviss、 Wisconsin- Whitewater大学的Gary Klatt、Kings学院的Mark Michael、 Shepherd学院的Peter Morris、 Missouri大学的Dix H. Pettey、Puget Sound大学的Matt Pickard、 Tennessee大学的Terry Walters、南Mississippi大学的Porter Webster、Frostburg州立大学的Richard Weimer、Wisconsin-Eau Claire大学的Thomas Weininger和Furman大学的Mark Woodard。本书第三版作了进一步改进，这得益于全美国各地本书的使用者的意见以及下列同行的评论意见：Wisconsin-Eau Claire大学的Veena Chadha、Michigan大学的Gary Chartrand、东南Louisiana大学的Tilak de Alwis、东Washington大学的Ron Dalla、 Evergreen 州立学院的George Dimdroff、Georgia州立大学的Gayla S. Domke、Texas大学Arlington分校的Jerome Eisenfeld、Frosthurg 州立大学的Kathleen Elder、George Mason大学的Klaus Fischer、北Virginia公立学院的 Donald A. Goral、南Florida大学的Natasa Jonoska、George Mason大学的Thomas Kiley、圣Mary’s学院的Theresa D. Magnus、Tennessee大学的Chris Mawata、北Carolina A & T大学的Robert C. Mers、Purdue大学Calumel分校的Catherine M. Murphy、 Pennsylvania Edinboro大学的Anne Quinn、Wright州立大学的Steen Pedersen、 Missouri大学Columbia分校的Dix H. Pettey、Bemidji州立大学的James L. Richards、Washburn大学的A. Allan Riveland、中部Michigan大学的Mohan Shrikhande和西Michigan大学的Allan Schwenk，以及我们的同事Roger Eggleton。 我们要对Illinois 州立大学的Michael Plantholt和Dean Sanders表示特别的感谢，他们独立地审核了第3版中的所有算法的正确性和可读性。他们的建议引发了对算法的实质性的修正和改进。 本书第4版的更改源于下列同行的评论意见：中西部州立大学的Mark Fenis、Georgia州立大学的Johanne Hartingh、圣Mary’s学院的Colleen Hoover、Truman州立大学的Jason Miller和太平洋联合学院的Richard Rockwell。 我们还要感谢Cindy Cody和Kevin Bradley在出版过程中出色的编辑工作。 John A.Dossey Albert D.Otto Lawrence E.Spence Charles Vanden Eynden 目录： 010219-01.txt 目 录 第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章 图 91 3.1 图及其表示 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章 树 157 4.1 树的性质 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 二叉树和遍历 197 4.5.1 表达式树 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章 匹配 230 5.1 相异代表系 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