图论算法理论,实现及应用

《图论算法理论、实现及应用》是北京大学出版社出版的图书，作者是王桂平 王 衍 任嘉辰。

• 作者 王桂平  王  衍  任嘉辰
• ISBN 978-7-301-17578-1/TP·1122
• 书名 图论算法理论、实现及应用
• 出版社 北京大学出版社

基本信息

　　本书系统地介绍了图论算法来自理论，并选取经典的ACM/ICPC竞赛题目为例题阐述图论算法思想，侧重于图360百科论算法的程序实现及应用。本书第1章介绍图论基本概念和图的两种存储表示方法:邻接矩阵和邻接表，第2~9章分别讨论图的遍历与活动网络，树与生成树问题，最短路径问题，可行遍性问题，网络流问题，点支配集、点覆盖集天香全征江绿先量、点独立集、边覆盖集、边独立集(匹配)，图的连通性问题，平面图与图的着色问题等。本书可以作为高等院校计算机(或相关专业)图论等相关课程的主教材，也可作为ACM/ICPC竞赛的辅导教材。

　倒水销挥动　基本信息

　　书 名:图论算法理论、实现及应用

　　标准书号:

　　定 价:5利于销节晶4.00元

目录

　　第1章 图的基本概念及图的存储... 1

　　1.1 基本概念... 1

　　1.1.1 有向图与无向图了突啊蛋移... 1

　　1.1.2 完外属房际村青约帝划多文全图、稀疏图、稠密图... 2

　　1.1.3 顶点与顶点、顶点与边的

　　关系... 3

　　1.1.4 顶点的度数及度序列... 3

　　1.1.5 二部图与完全二部图... 5

　　1.1.6 图的同构... 6

孔调脚由军　　1.1.7 子图与生成树... 6

　　1.1.8 路径几... 8

　　1.1.9 连通性... 8

　　1.1.10 权值、有向网与无向网... 10

　　1.2 图的存储表示... 10

　　1.2.1 邻接矩阵... 10

　　1.2.2 邻接表... 17

　　1.2.3 关于邻接矩阵和邻接表的

　　进一步讨论... 25

　　练习... 25

　　第2章 图的遍历与活动网络问题... 26

　　2.1 DFS遍历... 26

　　2.1.1 DFS算法思想... 26

　　2.1.2 DFS算城尼与八价夜下她括法的实现及复杂度

　　分析... 27

　　2.1.3 例题解析... 粮推它严相则氧热所30

　　练习... 40

　　2.2 BFS遍历... 43

　　2.吃地向万较2.1 BFS算法思想... 43

　　2.2.2 BFS算法的实现及复杂度

　　分析... 44

　　2.2.3 关于DFS算法和BFS算法

　　的说明... 46

　　2.2.4 例题解析..切严手右吃都. 46

　　练习... 60

　　2.3 活动网络--AOV网络... 66

　　2.3.1 AOV网络与拓扑排序... 66

　　2.3.2 拓扑排序实现方法... 68

　　2.3.3 关于拓扑排序的进一步说明... 73

　　2.类就神步增色问鲜今操3.4 例题解析... 74

　　练习... 82

蛋检烈香亲口军城　　2.4 活动网络--AOE网络... 84

　　2.4.1 AOE网络与关键路径... 84

　　2.4.2 关键路径求解方法... 85

　　第3章 树与图的生成树... 92

　　3.1 树与森林... 92

　　3.1.1 树... 92

　　3.1.2 森林... 92

　　3.2 生成胶歌增树及最小生成树... 93

　　3.2.1 生成论几树... 93

　　3.2.2 最小生成树.五.. 93

　　3.3 克鲁亮够护蛋司衡皇洲独永块斯卡尔(Kruskal)算法... 94

　　3.3.1 克鲁斯卡尔(Kru富skal)算法

　　思想... 94

　　3.3.2 等价类与并查集... 95

　　3.3.3 Kruskal算法实现... 99

　　3.3.4 Boruvka算法... 103

　　3.3.5 例题解析... 104

　　练习... 110

　　3.4 普里姆算法... 114

　　3.4.1 Prim算法思想... 114

　　3.4.2 普里姆(Prim)算法实现... 115

　　3.4.3 关于普里姆算法的进一步

　　讨论... 119

　　3.4.4 例题解析... 120

　　练习... 125

　　3.5 判定最小生成树是否唯一... 129

　　3.5.1 最小生成树不唯一的原因

　　分析... 129

　　3.5.2 判定最小生成树是否唯一的

　　方法... 130

　　3.5.3 例题解析... 132

　　第4章 最短路径问题... 137

　　4.1 边上权值非负情形的单源最短

　　路径问题-Dijkstra算法... 137

　　4.1.1 算法思想... 137

　　4.1.2 算法实现... 139

　　4.1.3 关于Dijkstra算法的

　　进一步讨论... 143

　　4.1.4 例题解析... 143

　　练习... 150

　　4.2 边上权值为任意值的单源最短

　　路径问题-Bellman-Ford算法... 154

　　4.2.1 算法思想... 154

　　4.2.2 算法实现... 156

　　4.2.3 关于Bellman-Ford算法的

　　进一步讨论... 160

　　4.2.4 例题解析... 163

　　练习... 171

　　4.3 Bellman-Ford算法的改进-

　　SPFA算法... 174

　　4.3.1 算法思想... 174

　　4.3.2 算法实现... 175

　　4.3.3 关于SPFA算法的进一步

　　讨论... 179

　　4.3.4 例题解析... 179

　　练习... 186

　　4.4 所有顶点之间的最短路径-

　　Floyd算法... 189

　　4.4.1 算法思想... 189

　　4.4.2 算法实现... 191

　　4.4.3 关于Floyd算法的进一步

　　分析... 194

　　4.4.4 例题解析... 194

　　练习... 202

　　4.5 差分约束系统... 208

　　4.5.1 差分约束系统与最短路径... 208

　　4.5.2 例题解析... 210

　　练习... 219

　　第5章 可行遍性问题... 223

　　5.1 欧拉回路... 223

　　5.1.1 基本概念及定理... 223

　　5.1.2 欧拉回路的判定... 227

　　练习... 234

　　5.2 欧拉回路的求解... 235

　　5.2.1 DFS搜索求解欧拉回路... 235

　　5.2.2 Fleury(佛罗莱)算法... 244

　　练习... 248

　　5.3 中国邮递员问题... 250

　　5.4 汉密尔顿回路... 251

　　5.4.1 基本概念及定理... 251

　　5.4.2 汉密尔顿回路求解... 253

　　第6章 网络流问题... 258

　　6.1 网络最大流... 258

　　6.1.1 基本概念... 259

　　6.1.2 最大流最小割定理... 263

　　6.1.3 网络最大流的求解... 264

　　6.1.4 一般增广路方法--

　　Ford-Fulkerson算法... 265

　　6.1.5 最短增广路算法... 273

　　6.1.6 连续最短增广路算法--

　　Dinic算法... 277

　　6.1.7 一般预流推进算法... 278

　　6.1.8 最高标号预流推进算法... 282

　　6.1.9 网络最大流算法总结... 283

　　6.1.10 例题解析... 283

　　练习... 299

　　6.2 最小割的求解... 303

　　练习... 316

　　6.3 流量有上下界的网络的最大流和

　　最小流... 318

　　6.3.1 流量有上下界的容量网络... 318

　　6.3.2 流量有上下界的网络的

　　最大流... 321

　　6.3.3 流量有上下界的网络的

　　最小流... 322

　　6.3.4 例题解析... 329

　　练习... 342

　　6.4 最小费用最大流... 343

　　6.4.1 基本概念... 343

　　6.4.2 最小费用最大流算法... 344

　　6.4.3 例题解析... 347

　　练习... 356

　　第7章 支配集、覆盖集、独立集与匹配... 360

　　7.1 点支配集、点覆盖集、点独立集... 360

　　7.1.1 点支配集... 360

　　7.1.2 点覆盖集... 362

　　7.1.3 点独立集... 363

　　7.1.4 点支配集、点覆盖集、

　　点独立集之间的联系... 365

　　7.2 点支配集、点覆盖集、点独立集的

　　求解... 365

　　7.2.1 逻辑运算... 365

　　7.2.2 极小点支配集的求解... 366

　　7.2.3 极小点覆盖集、极大点

　　独立集的求解... 366

　　7.3 边覆盖集与边独立集... 367

　　7.3.1 边覆盖集... 367

　　7.3.2 边独立集(匹配)368

　　7.3.3 最大边独立集(最大匹配)与

　　最小边覆盖集之间的联系... 370

　　7.4 匹配问题... 371

　　7.4.1 完美匹配... 371

　　7.4.2 二部图的完备匹配与

　　完美匹配... 372

　　7.4.3 最佳匹配... 372

　　7.4.4 匹配问题求解的基本概念及

　　思路... 372

　　7.5 二部图最大匹配问题的求解... 374

　　7.5.1 网络流解法... 374

　　7.5.2 匈牙利算法... 376

　　7.5.3 例题解析... 379

　　练习... 396

　　第8章 图的连通性问题... 402

　　8.1 基本概念... 402

　　8.1.1 连通图与非连通图... 402

　　8.1.2 无向图的点连通性... 403

　　8.1.3 无向图的边连通性... 405

　　8.1.4 无向图顶点连通性和

　　边连通性的联系... 406

　　8.1.5 有向图的连通性... 406

　　8.2 无向图点连通性的求解及应用... 407

　　8.2.1 关节点的求解... 407

　　8.2.2 重连通分量的求解... 414

　　8.2.3 顶点连通度的求解... 417

　　练习... 421

　　8.3 无向图边连通性的求解及应用... 424

　　8.3.1 割边的求解... 424

　　8.3.2 边双连通分量的求解... 428

　　8.3.3 边连通度的求解... 436

　　练习... 437

　　8.4 有向图强连通性的求解及应用... 440

　　8.4.1 有向图强连通分量的

　　求解算法... 440

　　8.4.2 有向图强连通分量的应用... 442

　　练习... 458

　　第9章 平面图及图的着色问题... 462

　　9.1 基本概念... 462

　　9.1.1 平面图与非平面图... 462

　　9.1.2 区域与边界... 463

　　9.1.3 极大平面图与极小非平面图... 464

　　9.1.4 平面图的对偶图... 464

　　9.1.5 关于平面图的一些定理... 465

　　9.2 欧拉公式及其应用... 465

　　9.2.1 欧拉公式... 465

　　9.2.2 欧拉公式的应用... 466

　　练习... 469

　　9.3 平面图的判定... 470

　　9.4 图的着色问题... 472

　　9.4.1 地图染色与四色猜想... 472

　　9.4.2 图的着色... 472

　　9.4.3 图着色的应用... 475

　　9.4.4 图着色求解算法及例题解析... 475

　　练习... 479

　　附录 本书例题和练习题目录... 482

　　索引... 489

　　参考文献 497