图论算法理论、实现及应用PDF|Epub|txt|kindle电子书版本网盘下载

图论算法理论、实现及应用PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第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关于邻接矩阵和邻接表的进一步讨论24

练习24

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

2.1 DFS遍历25

2.1.1 DFS算法思想25

2.1.2 DFS算法的实现及复杂度分析26

2.1.3例题解析29

练习38

2.2 BFS遍历41

2.2.1 BFS算法思想41

2.2.2 BFS算法的实现及复杂度分析42

2.2.3关于DFS算法和BFS算法的说明44

2.2.4例题解析45

练习58

2.3活动网络——AOV网络63

2.3.1 AOV网络与拓扑排序63

2.3.2拓扑排序实现方法65

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

2.3.4例题解析71

练习79

2.4活动网络——AOE网络81

2.4.1 AOE网络与关键路径81

2.4.2关键路径求解方法82

第3章 树与图的生成树88

3.1树与森林88

3.1.1树88

3.1.2森林88

3.2生成树及最小生成树89

3.2.1生成树89

3.2.2最小生成树89

3.3克鲁斯卡尔（Kruskal）算法90

3.3.1 Kruskal算法思想90

3.3.2等价类与并查集91

3.3.3 Kruskal算法实现95

3.3.4 Boruvka算法99

3.3.5例题解析99

练习105

3.4普里姆（Prim）算法109

3.4.1 Prim算法思想109

3.4.2 Prim算法实现110

3.4.3关于Prim算法的进一步讨论114

3.4.4例题解析114

练习119

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

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

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

3.5.3例题解析126

第4章 最短路径问题131

4.1边上权值非负情形的单源最短路径问题——Dijkstra算法131

4.1.1算法思想131

4.1.2算法实现133

4.1.3关于Dijkstra算法的进一步讨论137

4.1.4例题解析137

练习144

4.2边上权值为任意值的单源最短路径问题——Bellman-Ford算法148

4.2.1算法思想148

4.2.2算法实现150

4.2.3关于 Bellman-Ford算法的进一步讨论153

4.2.4例题解析156

练习164

4.3 Bellman-Ford算法的改进——SPFA算法167

4.3.1算法思想167

4.3.2算法实现167

4.3.3关于SPFA算法的进一步讨论171

4.3.4例题解析171

练习178

4.4所有顶点之间的最短路径——Floyd算法180

4.4.1算法思想180

4.4.2算法实现182

4.4.3关于Floyd算法的进一步分析185

4.4.4例题解析185

练习192

4.5差分约束系统198

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

4.5.2例题解析200

练习208

第5章 可行遍性问题212

5.1欧拉回路212

5.1.1基本概念及定理212

5.1.2欧拉回路的判定216

练习223

5.2欧拉回路的求解223

5.2.1 DFS搜索求解欧拉回路223

5.2.2 Fleury（佛罗莱）算法232

练习236

5.3中国邮递员问题237

5.4汉密尔顿回路238

5.4.1基本概念及定理239

5.4.2汉密尔顿回路求解241

第6章 网络流问题246

6.1网络最大流246

6.1.1基本概念247

6.1.2最大流最小割定理251

6.1.3网络最大流的求解252

6.1.4一般增广路方法——Ford-Fulkerson算法253

6.1.5最短增广路算法261

6.1.6连续最短增广路算法——Dinic算法264

6.1.7一般预流推进算法266

6.1.8最高标号预流推进算法270

6.1.9网络最大流算法总结270

6.1.10例题解析271

练习285

6.2最小割的求解289

练习301

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

6.3.1流量有上下界的容量网络304

6.3.2流量有上下界的网络的最大流307

6.3.3流量有上下界的网络的最小流307

6.3.4例题解析313

练习325

6.4最小费用最大流327

6.4.1基本概念327

6.4.2最小费用最大流算法328

6.4.3例题解析330

练习338

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

7.1点支配集、点覆盖集、点独立集342

7.1.1点支配集342

7.1.2点覆盖集344

7.1.3点独立集345

7.1.4点支配集、点覆盖集、点独立集之间的联系347

7.2点支配集、点覆盖集、点独立集的求解347

7.2.1逻辑运算347

7.2.2极小点支配集的求解348

7.2.3极小点覆盖集、极大点独立集的求解348

7.3边覆盖集与边独立集349

7.3.1边覆盖集349

7.3.2边独立集（匹配）350

7.3.3最大边独立集（最大匹配）与最小边覆盖集之间的联系352

7.4匹配问题353

7.4.1完美匹配353

7.4.2二部图的完备匹配与完美匹配354

7.4.3最佳匹配354

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

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

7.5.1网络流解法356

7.5.2匈牙利算法358

7.5.3例题解析361

练习377

第8章 图的连通性问题382

8.1基本概念382

8.1.1连通图与非连通图382

8.1.2无向图的点连通性383

8.1.3无向图的边连通性385

8.1.4无向图顶点连通性和边连通性的联系386

8.1.5有向图的连通性386

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

8.2.1关节点的求解387

8.2.2重连通分量的求解394

8.2.3顶点连通度的求解396

练习401

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

8.3.1割边的求解403

8.3.2边双连通分量的求解407

8.3.3边连通度的求解414

练习416

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

8.4.1有向图强连通分量的求解算法418

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

练习435

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

9.1基本概念438

9.1.1平面图与非平面图438

9.1.2区域与边界439

9.1.3极大平面图与极小非平面图440

9.1.4平面图的对偶图440

9.1.5关于平面图的一些定理441

9.2欧拉公式及其应用441

9.2.1欧拉公式441

9.2.2欧拉公式的应用442

练习445

9.3平面图的判定446

9.4图的着色问题447

9.4.1地图染色与四色猜想447

9.4.2图的着色448

9.4.3图着色的应用450

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

练习455

附录 本书例题和练习题目录457

索引461

参考文献469