[PDF] 图论与算法电子书

图论与算法

作者：程龚

页数：218

出版社：清华大学出版社

出版日期：2024

ISBN：9787302660439

高清校对版pdf（带目录）

前往页尾底部查看PDF电子书

内容简介

本书由实际问题展开，在介绍用图建立数学模型并阐述相关数学原理的基础上，进一步介绍用计算
机解决相关问题的方法，包括经典算法的设计和基于数学原理的算法分析，使理论与算法融会贯通，并
通过大量的思考题引导读者自己完成推导过程。
本书共 10 章：第 1 章介绍图的基本概念；第 2~4 章介绍图的连通性和遍历方法，包括基于圈的特
殊遍历方法；第 5 章介绍匹配；第 6 章和第 7 章分别介绍赋权图和有向图，包括流网络；第 8 章介绍独
立、覆盖和支配；第 9 章介绍边和顶点的染色；第 10 章介绍平面，包括面的染色。每节后均附有练习
题，包括理论题和编程练习题。
本书可作为高等学校计算机及相关专业本科生和研究生的教材。

作者简介

程龚，南京大学计算机科学与技术系教授，博士生导师。从事“图论”等课程教学工作十余年。荣获国家级教学成果奖二等奖、南京大学青年五四奖章。研究领域包括大数据搜索、知识图谱等。入选国家级青年人才计划，主持完成国家重点研发计划课题和多个国家自然科学基金项目，研究成果发表在The Web Conference、IEEE Transactions on Knowledge and Data Engineering等学术期刊，获国际会议最佳论文奖或提名7次，担任过国际语义网会议、全国知识图谱与语义计算大会等会议程序委员会主席。

本书特色

本书介绍了图论中的连通、匹配/独立、覆盖、支配、染色、平面等数学问题及相关的数学概念和重要定理，继而介绍了对应的计算问题及相关的经典算法的设计与分析，并通过大量的思考题引导读者开展自我探索和深入思考。（1）内容上，理论(数学)与算法(计算机)融会贯通：每章由实际问题开始，“理论”部分通过概念定理帮助读者建立实际问题背后的数学模型并掌握数学原理，然后“算法”部分通过算法设计与分析帮助读者掌握实际问题对应的算法问题的解法，理论与算法篇幅各半。（2）形式上，帮助读者通过自我探索完成知识内化：正文部分几乎没有形式化的证明，而是通过思考题引导读者自己完成推导过程，对部分思考题在附录部分给出提示或答案，其初衷是尽可能推迟向读者呈现答案，为读者保留更多思考机会，而非从外部直接灌输知识。本书特色：
（1）将实际问题建模为数学问题，进而解决其中的算法问题，使理论和算法融会贯通。
（2）将完整证明移至附录部分，正文通过思考题引导读者自己推导，有助于知识的内化。

第 1 章图的基本概念. 1
1.1 图的定义 2
1.2 图的表示 4
1.3 图的关系 7
1.4 图的运算 9
第 2 章连通和遍历. 12
2.1 连通和 DFS 13
2.1.1 理论 13
2.1.2 算法 14
2.2 割点和割边. 17
2.2.1 理论 17
2.2.2 算法 19
2.3 距离和 BFS 23
2.3.1 理论 23
2.3.2 算法 24
第 3 章圈和遍历. 30
3.1 圈和树 . 31
3.1.1 理论 31
3.1.2 算法 33
3.2 二分图 . 34
3.2.1 理论 34
3.2.2 算法 36
3.3 欧拉图 . 38
3.3.1 理论 38
3.3.2 算法 39
3.4 哈密尔顿图. 44
3.4.1 理论 44
3.4.2 算法 45
第 4 章连通度 . 46
4.1 块 46
4.1.1 理论 47
4.1.2 算法 49
4.2 割集和连通度 52
4.2.1 理论 52
4.2.2 算法 55
第 5 章匹配 57
5.1 匹配和最大匹配 58
5.1.1 理论 58
5.1.2 算法 59
5.2 完美匹配. 69
第 6 章赋权图 . 71
6.1 赋权图和距离 72
6.1.1 理论 72
6.1.2 算法 73
6.2 最小生成树. 76
6.2.1 理论 76
6.2.2 算法 77
6.3 赋权欧拉图. 82
6.3.1 理论 82
6.3.2 算法 83
6.4 赋权哈密尔顿图 85
6.4.1 理论 86
6.4.2 算法 86
第 7 章有向图 . 92
7.1 有向图的定义 92
7.2 有向图的表示 95
7.3 有向图的连通 96
7.3.1 理论 96
7.3.2 算法 98
7.4 有向图的距离 . 104
7.4.1 理论 . 104
7.4.2 算法 . 104
7.5 流网络和最大流. 105
7.5.1 理论 . 105
7.5.2 算法 . 109
第 8 章独立、覆盖和支配. 114
8.1 边的独立、覆盖和支配 115
8.1.1 理论 . 115
8.1.2 算法 . 118
8.2 顶点的独立、覆盖和支配 121
8.2.1 理论 . 122
8.2.2 算法 . 126
第 9 章染色 . 132
9.1 边的染色 133
9.1.1 理论 . 133
9.1.2 算法 . 135
9.2 顶点的染色 145
9.2.1 理论 . 145
9.2.2 算法 . 146
第 10 章平面 . 150
10.1 可平面图 . 150
10.1.1 理论. 150
10.1.2 算法. 154
10.2 面的染色 . 158
A 部分思考题提示 162
B 部分思考题完整证明 166
术语小结 209
参考文献 214

PDF更新中