本书是介绍离散数学理论和方法的经典教材,仅在美国就有600多所高校正在使用;目前,国内的众多大学也在采用其中文版作为教材。本书已经成为使用率最高的离散数学教材,在教学领域获得了极大的成功。 本书内容全面,第6版在前五版的基础上做了大量的改进,使其成为更有效的教学工具。
离散数学及其应用(原书第6版·本科教学版)
Discrete Mathematics and Its Applications Sixth Edition
(美)Kenneth H. Rosen 著 袁崇义 屈婉玲 张桂芸 等译 陈琼 改编
《离散数学及其应用》一书是介绍离散数学理论和方法的经典教材,已经成为采用率最高的离散数学教材,仅在美国就被600多所高校用作教材,并获得了极大的成功。第6版在前5版的基础上做了大量的改进,使其成为更有效的教学工具。
本书基于该书第6版进行改编,保留了国内离散数学课程涉及的基本内容,更加适合作为国内高校计算机及相关专业本科生的离散数学课程教材。
本书的具体改编情况如下:
第1章中补充了关于范式和标准型的基础内容。
删去了在其他课程中讲授的内容,如数论、离散概率、归纳和递归等。
对于保留章节,删去了编号为偶数的练习题。
删去了相关的历史资料。
作者简介:
Kenneth H. Rosen 密歇根大学数学学士,麻省理工学院数学博士。曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学,后加盟贝尔实验室,现为AT&T实验室特别成员。除本书外,他还著有《初等数论及其应用》等书,并担任CRC离散数学丛书的主编。
本书是根据我多年讲授离散数学的经验和兴趣写成的。对学生而言,我的目的是为他们提供准确而可读的教材,清晰地介绍离散数学的概念和技术。我的目标是向爱怀疑的学生们展示离散数学的实用性,希望为学习计算机科学的学生提供一切必需的数学基础,也希望学数学的学生理解数学概念的重要性,以及这些概念为什么对应用是重要的,还希望本书既能达到这些目标,又不含太多的水分。
对教师(指导者)而言,我的目的是使用成熟的数学教学技术设计一个灵活而全面的教学工具,希望为教师们提供能够以最适合特定学生特点的方式高效地讲授离散数学的教材。希望本书能够达到这些目标。
我为本教材在过去已经取得的巨大成功而分外高兴。根据成功使用本书的600多所学校的大批师生的反馈和建议,此次第6版进行了许多改进。很多内容有所提高,辅助材料更加丰富,配套网站提供的材料更有帮助性,使师生更容易达到他们的目标。
本教材是为1至2个学期的离散数学入门课程而设计的,适用于数学、计算机科学、工程等许多专业的学生。虽然唯一的先修课要求是大学代数,但是要想学习好离散数学还需要掌握更多的数学知识。
离散数学课的目标
离散数学课有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用,更重要的是,这样一门课应教会学生怎样进行数学逻辑思维。为此,本教材特别强调数学推理及用不同的方法解题。本教材有5个重要的主题交织在一起:数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程应该努力使这五部分内容相互融合、平衡。
1数学推理: 学生必须理解数学推理,以便阅读、理解和构造数学证明。本教材以数理逻辑开篇,在后面证明方法的讨论中,数理逻辑是基础。同时,本书描述了构造性证明的方法和技巧。本书还十分强调数学归纳法,不仅用许多证明的实例进行介绍,还详细地解释了数学归纳法为什么是有效的证明方法。
2组合分析:解题的一项重要技巧是计数或枚举对象。本书中,对枚举的讨论从基本的计数方法着手,重点是用组合分析方法来解决计数问题,而不直接使用公式。
3离散结构:离散数学课应该教会学生如何使用离散结构,即学会如何使用表示离散对象及其之间的关系的抽象数学结构。离散结构包括:集合、置换、关系、图、树和有限状态机等。
4算法思维:有些问题是通过详细说明其算法来求解的。算法在描述后就可构造计算机程序来实现。这一过程中用到的数学部分包括:算法描述、正确性证明以及执行算法所需要的计算机内存和时间的分析。这些内容在本书中均有介绍。算法是用英语和一种易于理解的伪码描述的。
译著中采用汉语。——译者注
5应用与建模:离散数学几乎应用在所有研究领域中。本书既介绍了其在计算机科学和数据网络中的许多应用,也介绍了在其他各种领域中的应用,如化学、植物学、动物学、语言学、地理、商业以及互联网等。这些均是离散数学的实际而重要的应用,而不是编造的。用离散数学来建模是十分重要的问题求解技巧。本书中的一些练习让学生有机会通过自己构造模型来掌握这一技巧。
本书特点
易入门实践证明:此课本对初学者来说易读易懂。它的大部分内容只要求学生学过大学代数,不需要其他的预备知识,少数几个涉及微积分的地方也有明确说明。大部分学生应该很容易理解课本中用于表示算法的伪码,不管他们是否学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易理解的水平开始。本书在仔细研究基本的数学概念之后,就介绍了其他领域中更难的部分和应用。
灵活性课本为灵活使用作了精心设计。各章对其前面内容的依赖都降到最低程度。每一章分成长度大致相等的若干节,每一节又根据内容划分成小节以方便教学。教师可以根据这些分块灵活地安排进度。
写作风格本书的写作风格是直接和实用。使用准确的数学语言,但没有过分的形式化与过分的抽象。在记号和数学命题的词汇间作了精心的平衡。
数学严谨性和准确性本书中所有定义和定理的陈述都十分详细,所以学生可以欣赏其语言的准确以及数学所需的严谨。但证明则是缓慢引入并展开的,每一步都经过了详细论证。本书解释并大量使用了递归定义。
实例本书使用了很多例子来阐述概念、建立不同内容之间的关系或导入应用。在大部分例子中,先提出问题,再适当给出它的解。
应用书中叙述的应用展示了离散数学在解决现实问题中的使用价值,所涉及的范围很广,包括计算机科学、数据网络、心理学、化学、工程、语言学、生物学、商业和互联网。
算法离散数学的结论常常要用算法来表示,因此,本书每一章都介绍了一些关键算法。书中还简要分析了所有算法的计算复杂性。
关键术语和结果每一章后面都列出了本章的关键术语和结果,但只列出了学生必须学会的那些最重要的关键术语,而不是在该章中定义的所有术语。
练习书中包含许多练习,代表了大量不同类型的问题。本书不仅提供了足够多的简单问题用于练习基本技巧,还提供了大量的中等难度的练习和许多有挑战性的练习。练习的叙述清晰而无歧义,并按难易程度进行了分级。有些特殊的论题还设计成系列练习。这些练习不仅给出了正文中没有介绍的新概念,还使学生可以通过自己的努力发现新思想。
比平均水平稍难的练习用单个星号作标记,相当有挑战性的问题则用两个星号来标记。必须用微积分来解的练习也作了明确说明。导出正文要用到的结果的练习则用符号“”识别。
复习题每章最后都有一组复习题。设计这些问题的目的是帮助学生重点学习该章最重要的概念和技术。要回答这些复习题,学生必须写出较长的答案,而只做点计算或简答是不够的。
计算机题目每一章后面还有一组计算机题目。这些题目把学生可能已经学到的有关计算和离散数学的内容联系起来。如果从数学角度或程序设计角度来看,其难度超过平均水平的计算机题目用一个星号标记,特别有挑战性的则用两个星号标记。
计算和研究每一章的结论部分都有一组计算和研究性问题。要完成这些练习(大约有100道)需要软件工具的帮助,例如学生或教师自己编写的程序,或数学计算软件包(如Maple或Mathematica)。大部分这样的练习为学生提供了通过计算发现新事实或新思想的机会。
写作题目每一章后面都有一组应该书面完成的题目。要完成这类题目,学生需要参考数学文献。有些题目在过去的历史上是很重要的,学生需要查找原始资料,其他的题目则是通往新内容和新思想的途径。所有此类练习均向学生展示正文中没有深入探讨的思想。这些题目把数学概念和书面写作的过程结合在一起,以帮助学生探索未来的研究领域。
推荐读物在正文的最后,专门有一节用来为各章推荐参考读物,其中有不超过本书水平的书籍,也有较难的书籍;有综述性文章,也有发表离散数学新发现的原始文章。其中一些是许多年前出版的经典读物,而其他一些是在最近几年内出版的。
配套网站
为本书开发了一个内容广泛的配套网站,该网站将不断地维护和改进。可以以多种方式使用该网站进一步学习离散数学,网站地址是:wwwmhhecom/rosen
由此地址进入该网站的主页。该网页有下列链接:
信息中心
学生中心
教师中心
信息中心:该中心包含本书及其辅助资料的基本信息。教师在这个网页中可以利用网页抽取系统“Page Out”,建立自己的课程网页,还能学习定制出版信息。从该信息中心出发,沿着适当的链接,可以看到本书网站的一个概观。
学生中心:该中心包含了可供学生使用的丰富资源,包括下列与课本紧密相关的资源(在课本中用相应的图标加以标记):
网络资源指南:该指南提供了数百个含相关资料的外部网站的链接。可以通过关键词浏览或访问这些链接,它们将把你带到包含下列信息的网站:历史及传记信息、谜题及问题、讨论、Java小程序、程序以及其他类型的资源。
额外的例子:这个网站包含了大量额外的例子。这些例子主要集中在学生经常需要的课外资料的领域。虽然大部分例子只是扩充了基本概念,但还有一部分十分具有挑战性。
额外的步骤:对一些困难的知识点,提供了更深入的解释帮助理解,尤其是一些特殊的证明和例子。
评估:提供对七个关键概念理解程度的评估。每个评估都提供了一个题库,其中的每个试题由两部分构成:先是一段简短的复习,然后是一个多选题。如果你选择的答案不正确,该系统还能提供建议,帮助你理解错在什么地方。这样的评估系统应该能诊断出你学习中的问题,从而把精力集中在寻找纠正办法上。
交互式演示:已经开发了八个交互式演示系统,你可以用它们考查一些重要算法是怎么工作的。这些演示都与课本中的相应材料相对应。
从该学生中心你可以访问网络教学系统“Net Tutor”。它提供了在线教学帮助。当你提问与课本内容相关的问题时,如果是在规定教学时间内,你会收到实时回答;否则稍后才会收到回答。
学生中心还支持能发布消息的公告板系统。使用该系统,你可以提出问题,还可以回答其他学生提出的问题。
除此之外,学生中心还包括下列资源:
证明书写指南
离散数学的常见错误
写作题目的建议
Maple软件
教师中心:除了包含学生中心和信息中心提供的所有链接外,网站中的教师中心还包含下列链接:
教学大纲样本
教学建议
《Applications of Discrete Mathematics》一书中的某些章节
写给学生
什么是离散数学?离散数学是数学中研究离散对象的部分。(这里“离散”的含义是“由不同的或不相连的元素组成”。)离散数学能解决的问题包括:
在计算机系统中,有多少种方式可以选择一个合法口令?
赢彩票的概率是多少?
两台计算机之间在网络上是否有通路?
怎样鉴别Email信息中的垃圾邮件?
怎样加密信息以避免不该收到的人读取该信息?
在某一交通系统下,两个城市之间的最短路径是什么?
怎样把整数序列按递增序排列?
完成上述排序需要多少步骤?
如何证明一个排序方法能正确地排序?
怎样设计两个整数相加的电路?
有多少合法的因特网网址?
你们将学习解决诸如以上问题要用到的离散结构和技术。
更一般地,在对对象进行计数时要用到离散数学,研究两个有限(或可数)集合之间的关系时要用到离散数学,分析只含有限步的进程时也要用到离散数学。离散数学的重要性还在不断增加,一个关键原因就是计算机以离散的方式存储和处理信息。
为什么要学离散数学?有几条重要的理由来说明需要学习离散数学。首先,通过这个课程你们可以发展自己的数学素质,即理解和创造数学证明的能力。没有这些技巧,你们在学习数学时不可能太深入。
其次,离散数学是学习所有更高级数学课程的必经之路。离散数学为学习计算机科学课程提供必要的数学基础,这些课程包括:数据结构、算法、数据库理论、自动机理论、形式语言、编译理论、计算机安全以及操作系统。学生如果没有适当的离散数学基础,在学习上述课程时会感到很困难。有个学生给我发电子邮件说,在她学习的每一门计算机科学的课中都用到了本书的知识。
以离散数学为基础的数学课程包括逻辑、集合论、数论、线性代数、抽象代数、组合论、图论及概率论(其离散部分)。
此外,离散数学还包括了解运筹学(包括许多离散优化技术)、化学、工程及生物学等领域问题的必要的数学背景。从本书中你将学到在上述某些领域中的应用。
许多学生都感到,与他们以前学过的课程相比,离散数学入门课程的挑战性要大得多。这是因为,本课程的一个主要目的是教你进行数学推理和问题求解,而不只是一些分散的技巧。从课本中练习的设计可以看出这个目的。课本中虽然有大量与重点例子类似的练习,但还是有相当比例的练习需要创造性思维。这是有意设计的。虽然课本中的材料提供了解这些问题的工具,但你的任务是创造性地使用这些工具并取得成功。本课程的另一个主要目的是学会处理你以前没有见过的问题。然而,只学会解特殊类型的练习还无法保证能学会足够多的解题技巧,也不能保证在后继课程的学习中或在将来的职业生涯中取得成功。虽然课本讨论了许多主题,但离散数学是一个极为广泛且充满变化的研究领域。作为作者,我的任务之一是帮助你开发学习新知识的能力,在将来的奋斗中你十分需要新的知识。
练习我愿意就如何学好离散数学(或数学的其他学科和计算机科学)给同学们提点有益的建议。积极地做练习能使你最大地获益。我建议你尽可能地多做练习。在做完老师布置的练习后,我鼓励你做更多的练习,包括本书每节后面的练习和每章后面的补充练习。(注意练习前面的分级标记。)
练习标记含义
无标记常规练习
*较难的练习
**富有挑战性的练习
正文中要用到该练习的某个结论
(需要用到微积分)解题时要用到极限或微积分的概念
解题时,最好在查阅答案以前,自己先进行尝试。华章网站(wwwhzbookcom)提供了练习的答案。注意,只是答案,而不是完整解答。特别地,答案中省略了解的推导过程。
网络资源我强烈推荐你利用网络提供的新资源,特别是专为本书设计的网站http://www.mhhe.com/rosen中的资源。其中为澄清关键的概念设计了许多额外的例子,自我评测是考查你对关键问题的掌握程度;交互演示小程序帮你探索关键算法和其他概念;网络资源向导包含了广泛的与离散数学有关的外部链接;额外的解释和实践会帮助你掌握关键的概念,增加的书写证明可以避免离散数学中的一般错误;重要应用的深入探索指导应用Maple软件探索离散数学中的计算问题。在文中这些额外的在线资源尽可能在边缘处用特定图标标识。
本书的价值我希望你对本书的投资能得到优质的回报。我们花了多年的努力来开发和优化本书及其配套的辅助读物和网站。对大多数人来说,我很自信本书及其配套资料对掌握离散数学大有帮助。即使你现在的课程可能略去了其中某些章节,但当你学习新课程时会发现,阅读本书中的相关章节对新课程仍然十分有益,许多学生都有这样的感觉。许多人会在将来的研究工作时又找到本书,把它当做一本有用的工具书,特别是那些继续学习计算机科学、数学或工程的人。我设计本书作为你将来研究和探索的入门,我希望你能幸运地开始你的征程。
致谢
我要感谢很多学校中使用本书的大批师生们,他们向我提出了宝贵的反馈和有益的建议。没有他们的反馈和建议,本书不可能有很大的改进。我要特别感谢Jerrold Grossman、John Michaels和Geoge Bergman,感谢他们对第6版的技术审阅,他们敏锐的目光确保了本书的准确性。我也要感谢通过网站提交评论的人们提供的帮助。
我感谢本书第6版及前面5版的许多评阅人,他们对我提出了许多有益的批评和鼓励,我希望本版不辜负他们的期望。
我还要感谢McGrawHill出版社高等教育组的工作人员对本课题强有力的支持。特别要感谢出版人Liz Haefele的支持,感谢Liz Covello 和Senior Sponsoring编辑的提倡和热情,感谢开发编辑Dan Seibert的献身和关注,还要感谢原编辑Wayne Yuhasz,是他的洞察力和技巧保证了本书的成功,以及本书前几版的其他编辑。
我还要对制作本书第6版做出过贡献的职员表示感谢,他们有:项目总经理Peggy Selle、高级设计师Michelle Whitaker、媒体制作负责人Jeff Huettman、高级媒体项目经理Sandy Schnee、补充读物协调人Melissa Leick以及出色的市场经理Kelly Brown。我还很感谢Jerry Grossman,他检查了全部初稿以保证准确性,感谢校对员Rose Kramer 和 Gayle Casel。
Kenneth HRosen
计算机\离散数学
《离散数学及其应用》一书是介绍离散数学理论和方法的经典教材,已经成为采用率最高的离散数学教材,仅在美国就被600多所高校用作教材,并获得了极大的成功。第6版在前5版的基础上做了大量的改进,使其成为更有效的教学工具。
本书基于该书第6版进行改编,保留了国内离散数学课程涉及的基本内容,更加适合作为国内高校计算机及相关专业本科生的离散数学课程教材。本书的具体改编情况如下:
• 补充了关于范式和标准型的基础内容。
• 删去了在其他课程中讲授的内容,如数论、离散概率、归纳和递归等。
• 对于保留章节,删去了编号为偶数的练习题。
• 删去了相关的历史资料。
(美)Kenneth H.Rosen 著:Kenneth H. RoSen 1972年获密歇根大学数学学士学位,1976年获麻省理工学院数学博士学位,1982年加入贝尔实验室,现为AT&T实验室特别成员,国际知名的计算机数学专家。Rosen博士对数论领域与数学建模领域颇有研究,并写过很多经典论文及专著。除本书外,还著有经典著作《离散数学及其应用》(中文版和影印版均已由机械工业出版社引进出版)。
袁崇义 屈婉玲 张桂芸 等译 陈琼 改编:暂无简介
离散数学被IEEE&ACM确定为计算机专业核心课程,也是《中国计算机科学与技术学科教程2002》中界定的计算机科学与技术专业的核心基础课程。离散数学为许多专业课程提供理论基础,尤其是大多数算法的基础,可以说,不理解算法背后的数学含义,就不能理解算法的本质,而这种表面的一知半解很可能会给你带来很大的麻烦。本书的写作目标就是向读者展示离散数学的实用性:为计算机专业学生提供一切必要的数学基础,使数学专业学生理解数学概念的重要性以及这些概念为什么对应用而言是重要的。
本书译自Kenneth H. Rosen所著的《Discrete Mathematics and Its Applications, Sixth Edition》,是介绍离散数学理论和方法的经典教材,已经成为世界上使用率最高的离散数学教材之一,目前已用五种语言出版,发行30多万册,仅在美国就被600多所高校用作教材,并获得了极大的成功。国内很多院校也选择这本书作为教材。
这本书是计算机理论中一本很好的入门教材,几乎涉及计算机理论的所有方面。该书有如下几个特点:
1)通俗易懂,深入浅出。问题的引入、概念的描述和定理的阐述等通俗而不失科学性。
2)书中例子很多,而且非常实用,还包含了世界名题和一些趣味性很强的问题。
3)信息量虽然很大,但安排灵活,读者可以根据自己的兴趣选择性地学习。
4)涉及面特别广,可以使读者大致了解计算机理论的方方面面,有助于读者理解计算机科学与技术中蕴含的数学思想、数学思维,培养读者对问题的数学建模能力,激发读者学习其他课程的兴趣。
5)习题相当丰富,形容为“触目惊心”也不为过。题量大、题型多,有基础的也有探究的,有理论的也有实践的,正像作者在前言中强调的那样,他相当重视练习。
整本书阅读顺畅,行文活泼,作为参考书查阅也很方便。但书中多数章节还仅仅是相关的基础知识,也就是说,对这本书中的每一个知识点,比如逻辑、函数、组合数学、概率、算法等,都可以进行延伸阅读。有兴趣的话,读者不妨顺着书后的推荐阅读列表,继续深入下去。最后建议大家花些时间仔细读读前言,这对你用好本书、更好地学习离散数学等非常有帮助。
本书第5版主要由袁崇义、屈婉玲、王捍贫和刘田翻译完成,而第6版的翻译工作是在第5版译稿的基础上进行的,主要由张桂芸、赵子平、裴伟东、徐计和王向云翻译完成,张桂芸做了全书的统稿和定稿工作。由于翻译水平和时间有限,书中难免有不妥的地方,敬请读者不吝赐教。
译者
2011年5月于天津
出版者的话
改编者序
译者序
前言
第1章基础:逻辑和证明
11命题逻辑
111引言
112命题
113条件语句
114复合命题的真值表
115逻辑运算符的优先级
116翻译语句
117系统规范说明
118布尔检索
119逻辑难题
1110逻辑运算和位运算
练习
12命题等价
121引言
122逻辑等价
123德摩根律的运用
124构建新的逻辑等价式
练习
13谓词和量词
131引言
132谓词
133量词
134其他量词
135约束论域量词
136量词的优先级
137绑定变量
138涉及量词的逻辑等价
139否定量化表达式
1310翻译语句为逻辑表达式
1311在系统说明中运用量词
1312选自Lewis Carroll的例子
1313逻辑程序设计
练习
14嵌套量词
141引言
142量词的顺序
143将数学语句翻译成涉及嵌套量词的语句
144将嵌套量词翻译为汉语
145将汉语语句翻译成逻辑表达式
146否定嵌套量词
练习
15推理规则
151引言
152命题逻辑的有效论证
153命题逻辑的推理规则
154用推理规则建立论证
155消解
156谬误
157带量词命题的推理规则
158命题推理和量化语句推理规则的结合
练习
16证明导论
161引言
162一些专用术语
163定理陈述的理解
164证明定理的方法
165直接证明
166反证法
167归谬证明
168证明中的错误
169仅仅是开始
练习
17证明的方法和策略
171引言
172穷举证明和分情形证明
173存在性证明
174唯一性证明
175证明策略
176寻找反例
177行动证明策略
178填充
179未解决问题的作用
1710其他证明方法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第2章基本结构:集合、函数、数列与求和
21集合
211引言
212幂集合
213笛卡儿积
214使用带量词的集合符号
215量词的真值集合
练习
22集合运算
221引言
222集合恒等式
223扩展的并集和交集
224计算机表示集合的方式
练习
23函数
231引言
232一对一函数和映上函数
233反函数和函数组合
234函数的图像
235几个重要的函数
练习
24序列与求和
241引言
242序列
243特殊的整数序列
244求和
245基数
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第3章计数
31计数基础
311引言
312基本的计数原则
313比较复杂的计数问题
314容斥原理
315树图
练习
32鸽巢原理
321引言
322广义鸽巢原理
323巧妙使用鸽巢原理
练习
33排列与组合
331引言
332排列
333组合
练习
34二项式系数
341二项式定理
342帕斯卡恒等式和三角形
343其他的二项式系数恒等式
练习
35排列与组合的推广
351引言
352有重复的排列
353有重复的组合
354具有不可区别物体的集合的排列
355把物体放入盒子
练习
36生成排列和组合
361引言
362生成排列
363生成组合
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第4章高级计数技术
41递推关系基础
411引言
412递推关系
413用递推关系构造模型
练习
42求解线性递推关系
421引言
422求解常系数线性齐次递推关系
423常系数线性非齐次的递推关系
练习
43分治算法和递推关系
431引言
432分治递推关系
练习
44生成函数
441引言
442关于幂级数的有用事实
443计数问题与生成函数
444使用生成函数求解递推关系
445使用生成函数证明恒等式
练习
45容斥
451引言
452容斥原理
练习
46容斥原理的应用
461引言
462容斥原理的另一种形式
463埃拉托色尼筛
464映上函数的个数
465错位排列
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第5章关系
51关系及其性质
511引言
512函数作为关系
513集合的关系
514关系的性质
515关系的组合
练习
52n元关系及其应用
521引言
522n元关系
523数据库和关系
524n元关系的运算
525SQL
练习
53关系的表示
531引言
532用矩阵表示关系
533用图表示关系
练习
54关系的闭包
541引言
542闭包
543有向图的路径
544传递闭包
545沃舍尔算法
练习
55等价关系基础
551引言
552等价关系
553等价类
554等价类与划分
练习
56偏序
561引言
562字典顺序
563哈塞图
564极大元素与极小元素
565格
566拓扑排序
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第6章图
61图和图模型
练习
62图的术语和几种特殊的图
621引言
622基本术语
623一些特殊的简单图
624偶图
625特殊类型的图的一些应用
626从旧图到新图
练习
63图的表示和图的同构
631引言
632图的表示
633邻接矩阵
634关联矩阵
635图的同构
练习
64连通性
641引言
642通路
643无向图的连通性
644有向图的连通性
645通路与同构
646计算顶点之间的通路数
练习
65欧拉通路与哈密顿通路
651引言
652欧拉通路与欧拉回路
653哈密顿通路与哈密顿回路
练习
66最短通路问题
661引言
662最短通路算法
663旅行商问题
练习
67可平面图
671引言
672欧拉公式
673库拉图斯基定理
练习
68图着色
681引言
682图着色的应用
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第7章树
71概述
711树作为模型
712树的性质
练习
72树的应用
721引言
722二叉搜索树
723决策树
724前缀码
725博弈树
练习
73树的遍历
731引言
732通用地址系统
733遍历算法
734中缀、前缀和后缀记法
练习
74生成树
741引言
742深度优先搜索
743宽度优先搜索
744回溯
745有向图中的深度优先搜索
练习
75最小生成树
751引言
752最小生成树算法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
练习题答案
见华章网站wwwhzbookcom。