[离散数学] 图论代数结构

《[离散数学] 图论代数结构》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论与代数结构戴一奇胡冠章陈卫清华大学出版社(京)新登字158号内容简介离散数学是计算机专业的主要数学基础,本书与“数理逻辑与集合论”一起构成了清华大学计算机系的离散数学教材,全书共分10章:图论的基本概念;道路与回路;树;平面图与图的着色;匹配与网络流;图的连通性;代数结构预备知识;群;环和域;格与布尔代数。全书结构紧凑、内容精炼、证明严谨、语言流畅。为了便于读者理解和掌握基本理论,书中提供了丰富的例题,同时给出了众多良好的图算法,并进行了复杂性分析。此外,每章附有较多习题,其难度恰当。本书可作为计算机专业学生的教科

2、书或参考书,也可供计算机工程技术人员作为参考。图书在版编目(CIP)数据图论与代数结构/戴一奇等编著。—北京:清华大学出版社,1995ISBN7-302-01814-6Ⅰ.图⋯Ⅱ.戴⋯Ⅲ.①图论②代数-结构(数字)Ⅳ.①0157.5②015中国版本图书馆CIP数据核字(95)第03642号出版者:清华大学出版社(北京清华大学校内,邮编100084)印刷者:北京通县宏飞印刷厂发行者:新华书店总店北京科技发行所开本:787×10921/16印张:14.25字数:335千字版次:1995年8月第1版1997年12月第2次印刷

3、书号:ISBN7-302-01814-6/TP·810印数:4001～6000定价:12.90元前言离散数学是计算机专业的基础数学课程,它以离散量为研究对象,主要包括数理逻辑、集合论、图论和代数结构四部分内容。清华大学计算机科学与技术系把离散数学安排为“数理逻辑与集合论”,“图论与代数结构”两门课程,分两个学期讲授,各占50学时。本书分两大部分,其中一～六章是图论,在第一章介绍了图的基本概念及其代数表示方法,第二至第六章分别详细讨论了道路与回路、树、平面图与图的着色、匹配与网络流、图的连通性等图论的主要内容,并且将它们

4、与计算机的应用紧密结合,分析介绍了众多良好的图算法,给出其正确性证明与复杂度分析,这样,使读者在图的应用及算法的设计与分析方面能得到较好的训练与培养。第七～十章是代数结构部分,主要讨论了群、环和域、格与布尔代数等内容,它们都是抽象代数的基本内容,是计算机科学的重要数学基础。书中给出了大量的例题,它们不但有助于对概念的理解,同时也帮助读者掌握不同的证明方法。各章后面附有较多的习题,有难有易,同时还有一定数量的上机题,可以帮助读者熟悉掌握图的编程技巧。本书是作者在使用多年“图论与代数结构”讲义的基础上完成的。其中戴一奇修改

5、了第一～六章,胡冠章修改第七～九章,并审定了全书,陈卫修改了第十章。在出版过程中,得到了周远清教授和林行良教授的热情支持,贾志红同志完成了全部书稿的输入与排版,在此一并表示感谢。由于水平所限,本书难免出现错误与缺点,恳切希望得到广大读者,特别是讲授此课程教师们的批评与指正。·Ⅰ·目录第一章基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(1)1.1图的概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(1)1.2图的代数表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(5)习题一⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

6、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(9)第二章道路与回路⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(11)2.1道路与回路⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(11)2.2道路与回路的判定⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(13)2.3欧拉道路与回路⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(16)2.4哈密顿道路与回路⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(18)2.5旅行商问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(21)2.6最短路径⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(24)2.

7、7关键路径⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(28)2.8中国邮路⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(32)习题二⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(35)第三章树⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(38)3.1树的有关定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(38)3.2基本关联矩阵及其性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(39)3.3支撑树的计数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(41)3.4回路矩阵与割集矩阵⋯⋯⋯⋯⋯⋯⋯⋯

8、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(46)3.5支撑树的生成⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(52)3.6Huffman树⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(56)3.7最短树⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(59)3.8最大分枝⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(62)习题三⋯⋯⋯⋯⋯⋯