图论及应用【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

图论及应用PDF格式电子书版下载

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

第1章 图1

1.1图的定义和术语1

1.1.1图的定义1

1.1.2特殊的图2

1.1.3有向图和无向图3

1.1.4路径与连通3

1.2图的存储结构4

1.2.1邻接矩阵4

1.2.2前向星5

1.2.3邻接表7

1.3图的遍历13

1.3.1图的深度优先遍历13

1.3.2图的宽度优先遍历14

1.3.3图的拓扑排序15

1.3.4图的可行遍性20

第2章 树33

2.1树的定义和遍历33

2.1.1树的相关定义33

2.1.2树的遍历34

2.2图的生成树39

2.2.1最小生成树39

2.2.2次小生成树47

2.2.3有向图的最小树形图53

2.3树的其他问题60

2.3.1树上两点的最近公共祖先60

2.3.2树的最小支配集，最小点覆盖与最大独立集66

第3章 图的最短路径问题78

3.1单源最短路径78

3.1.1 Dijkstra算法78

3.1.2 Bellman-Ford算法83

3.1.3 SPFA算法85

3.1.4例题88

3.2每对顶点间的最短距离90

3.2.1 Floyd算法90

3.2.2例题92

3.3最短路问题的扩展与应用94

3.3.1 k短路95

3.3.2差分约束系统99

3.3.3 DAG图上的单源最短路径104

3.3.4 Floyd求最小环108

第4章 连通性问题112

4.1图的强连通112

4.1.1强连通的定义112

4.1.2 Kosaraju算法112

4.1.3 Tarjan算法115

4.1.4 Garbow算法118

4.1.5例题120

4.2最小点基125

4.2.1最小点基的定义125

4.2.2最小点基126

4.2.3最小权点基126

4.2.4例题126

4.3图的双连通131

4.3.1双连通的定义131

4.3.2点双连通分量132

4.3.3边双连通分量134

4.3.4例题136

4.4图的全局最小割问题和Stoer-Wagner算法142

4.5 2-SAT146

4.5.1 SAT146

4.5.2 2-SAT147

4.5.3例题147

第5章 网络流151

5.1网络151

5.1.1容量与流151

5.1.2残留网络及增广路152

5.1.3最小割最大流定理153

5.2最大流算法154

5.2.1 Ford-Fulkson方法的基本思想154

5.2.2 Edmond-Karp算法155

5.2.3 SAP算法及其优化157

5.2.4 Dinic算法160

5.2.5例题与应用163

5.3有上下界的网络流176

5.3.1解决上下界网络流的一般思路176

5.3.2例题与应用179

5.4网络的费用流181

5.4.1连续最短路算法181

5.4.2例题与应用186

第6章 二分图及匹配算法195

6.1匹配问题195

6.2匹配基本定理197

6.2.1 Berge定理197

6.2.2 Hall定理198

6.3二分图最大匹配199

6.3.1匈牙利算法199

6.3.2 Hopcroft-Karp算法206

6.3.3二分图多重匹配212

6.3.4二分图最大匹配的网络流解法217

6.4二分图最佳匹配218

6.4.1 Kuhn Munkras算法218

6.5二分图模型的应用228

6.5.1二分图最小点覆盖228

6.5.2有向无环图的最小路径覆盖231

6.5.3二分图的最大独立点集234

6.5.4最小点权覆盖236

参考文献238