|
| 編輯推薦： |
|
清华大学崔勇教授和张小平研究员合力打造，非常有启发性的一本教材。
|
| 內容簡介： |
|
图论与代数结构是离散数学的主要组成部分，是计算机科学的数学基础。全书共 9 章，第 1~6 章 为图论部分，包括图论基本概念、道路与回路、树、平面图与图的着色、匹配、网络流；第 7~8 章为 代数结构，包括代数结构预备知识和群论基础；第 9 章为图论编程实验。 全书结构紧凑、内容精练、证明严谨。为了便于读者理解和掌握，书中提供了丰富的例题，给出 了许多经典的算法，并附有许多不同难度的习题，供读者选择使用。 本书可作为计算机专业学生的教科书或参考书，也可供计算机工程技术人员作参考。
|
| 目錄：
|
第 1 章 基本概念 1
1.1 图的概念 1
1.2 图的代数表示 8
习题 1 13
第 2 章 道路与回路 16
2.1 图的连通性 16
2.2 道路与回路的判定 22
2.3 欧拉道路与回路 26
2.4 哈密顿道路与回路 29
2.5 旅行商问题 33
2.6 最短路径 37
2.7 关键路径 42
2.8 中国邮路 46
习题 2 50
第 3 章 树 59
3.1 树的有关定义 59
3.2 基本关联矩阵及其性质 61
3.3 支撑树的计数 63
3.4 回路矩阵与割集矩阵 68
3.5 Huffman 树 76
3.6 最短树 78
习题 3 82
第 4 章 平面图与图的着色 88
4.1 平面图 88
4.2 极大平面图 89
4.3 非平面图 91
4.4 对偶图 93
4.5 色数与色数多项式 98
习题 4 103
第 5 章 匹配 107
5.1 二分图的最大匹配 107
5.2 完全匹配 110
5.3 最佳匹配及其算法 112
习题 5 119
第 6 章 网络流 122
6.1 网络流图 122
6.2 Ford-Fulkerson 最大流标号算法 125
6.3 最大流的 Edmonds-Karp 算法 128
6.4 最大流的 Dinic 算法 131
6.5 最小费用流 134
习题 6 137
第 7 章 代数结构预备知识 139
7.1 集合与映射 139
7.2 等价关系 143
7.3 代数系统的概念 146
7.4 同构与同态 149
习题 7 154
第 8 章 群 156
8.1 半群 156
8.2 群、群的基本性质 161
8.3 循环群和群的同构 167
8.4 变换群和置换群 Cayley 定理 173
8.5 陪集和群的陪集分解 Lagrange 定理 179
8.6 正规子群与商群 184
8.7 群的同态和同态基本定理 187
8.8 群的直积 193
8.9 环和域 195
习题 8 199
第 9 章 图论编程实验 203
9.1 图的代数表示 203
9.2 最短路径问题 203
9.3 欧拉回路 204
9.4 最优二叉树 205
9.5 最短树 205
9.6 二分图匹配 205
9.7 网络流 206
9.8 挑战实验：俄罗斯方块 206
9.9 挑战实验：欧拉回路加强版 206
9.10 挑战实验：游走问题 207
参考文献 208
|
| 內容試閱：
|
“离散数学”是计算机专业的基础数学课程，它以离散量为研究对象，主要包括数理逻辑、集合论、图论和代数结构四部分内容。清华大学计算机科学与技术系把“离散数学”安排为“数理逻辑与集合论”和“图论与代数结构”两门课程，分两个学期讲授，各占48学时。
本书第1～6 章是图论部分，第1 章介绍了图的基本概念及其代数表示方法，第2～6章分别详细讨论了道路与回路、树、平面图与图的着色、匹配和网络流等图论的主要内容，并将它们与计算机应用紧密结合，分析介绍了经典的图论算法，给出其正确性证明与复杂性分析；第7～8 章是代数结构部分，主要讨论了群论的基础内容，这是抽象代数的重要内容，也是计算机科学的重要数学基础；第9 章为图论编程实验，设计了10 组不同难度的图论编程实验供读者选用，包含7 组针对前6 章图论内容设计的专题实验和3 组具有一定难度的综合性编程实验，这些实验能够使读者在图论算法的设计、分析、编程和应用等方面得到较好的训练与培养。书中给出了大量的例题，它们不但有助于读者对概念的理解，同时也帮助读者掌握不同的证明方法。各章后面附有较多的习题，并标注了习题的难度，供读者参考选用。
本书在戴一奇主持编著的《图论与代数结构》教材基础上修订完成。其中，崔勇修订了图论部分第1～6 章，并新增了第9 章图论编程实验；张小平修订了第1～8 章代数结构内容，并由戴一奇审定了全书。
本书有配套教学PPT、配套线上实验系统等辅助教学资源和读者服务社群，可通过如下二维码获取。
由于水平所限，本书难免出现错误，恳切希望得到广大读者，特别是讲授此课程教师们的批评与指正。
作者
2022 年1 月
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
