图和网络及其应用PDF电子书下载

算法7.15 最小覆盖的启发式算法 1

1.1 什么是图 1

第一章 图的基本概念 1

算法7.17 最小覆盖的启发式算法 2

算法7.16 用关联矩阵实现算法7.15求最小覆盖的算法 2

1.2 图的定义 2

1.3 子图及其运算 4

1.4 有向图 6

1.5 顶点度 8

1.6 连通性 9

1.7 圈和余圈 13

1.8 图的矩阵表示 17

1.9 图的同构 23

习题一 25

第二章 树及其应用 30

2.1 树 30

2.2 分离点和桥 31

2.3 块 33

2.4 基本圈和基本余圈 35

2.5 有向树 37

2.6 应用——最短路问题之一 40

算法2.1 Dijkstra算法——求某一顶点到其余顶点的最短路 42

2.7 应用——最短路问题之二 42

算法2.2 Floyd算法——求任意两顶点间的最短路 46

2.8 应用——最小生成树 46

算法2.3 Kruskal算法——求最小生成树 48

2.9 应用——最优2元树 48

习题二 51

算法2.4 Huffman算法——求最优2元树 51

第三章 圈空间和余圈空间及其应用 56

3.1 闭迹向量和边割向量 56

算法3.1 求圈矩阵的算法 60

算法3.2 求余圈矩阵的算法 60

3.2 圈基和余圈基 60

3.3 环流和势差 61

3.4 圈空间和余圈空间 65

3.5 应用——生成树的数目 66

3.6 应用——矩阵之间的关系 69

习题三 71

第四章 匹配及其应用 76

4.1 最大匹配 76

4.2 完美匹配 77

4.3 偶图的匹配 78

4.4 应用——人员分配问题之一 80

算法4.1 Hungarian方法——求偶图的完美匹配 82

4.5 应用——人员分配问题之二 82

4.6 应用——最优分配问题 83

算法4.2 求偶图的最大匹配的算法 83

算法4.3 可行顶点标号法——求赋权完全偶图的最优匹配 85

4.7 应用——配对问题 85

算法4.4 合理路——求图的最大匹配的算法 93

算法4.5 花——求图的最大匹配的算法 93

4.8 应用——最优配对问题 93

算法4.6 求最大权匹配的算法 98

习题四 98

第五章 平面图及其应用 103

5.1 平面图和可平面图 103

5.2 Euler公式 105

5.3 Kuratowski定理 106

5.4 对偶图 109

5.5 平面图的其它刻划 111

5.6 应用——电网络方程 112

5.7 应用——平面性判定 117

算法5.1 Dunn-Chan平面性判定的算法 120

习题五 120

6.1 图的算法与有效性 123

第六章 图的基本算法 123

6.2 图在计算机中的表示 125

6.3 图的遍历 126

算法6.1 遍历图的广度优先搜索法 129

算法6.2 遍历图的深度优先搜索法 129

6.4 连通性算法 129

算法6.3 连通性的融合顶点法 132

6.5 强连通性算法 132

算法6.4 求可达矩阵的逻辑算法 134

算法6.5 强连通性的逻辑算法 134

6.6 求生成树（林） 134

算法6.7 深度优先生成树算法 138

算法6.6 边生长算法 138

算法6.8 广度优先生成树算法 138

6.7 求全部生成树 138

算法6.9 求全部生成树的深度优先搜索法 143

6.8 求基本圈 143

算法6.10 求基本圈的广度优先搜索法 144

6.9 求有向圈 144

6.10 可分性算法 147

算法6.11 求有向圈的深度优先搜索法 147

算法6.12 可分性的基本圈标号法 148

习题六 148

第七章 图论模型 152

7.1 欧拉图 152

算法7.1 一笔画算法 154

7.2 计算机鼓轮设计 154

算法7.2 计算机鼓轮设计的算法 156

7.3 道路单行化问题 156

算法7.3 道路系统单行化的算法 157

7.4 储存问题 157

算法7.5 求最小覆盖的逻辑算法 162

算法7.7 求色数的逻辑算法 162

7.5 排课表问题 162

算法7.6 求最大独立集的逻辑算法 162

算法7.4 求色数的深度优先搜索法 162

算法7.8 求偶图的边色数的算法 167

算法7.9 排课表的算法 167

7.6 中国邮递员问题 167

算法7.10 中国邮递员问题的算法 168

7.7 循环赛排名问题 168

算法7.11 求有向哈密顿路的算法 171

算法7.12 循环赛排名的算法 171

7.8 旅行推销员问题 171

算法7.13 旅行推销员问题的近似算法 174

算法7.14 旅行推销员问题的分枝定界法 174

7.9 拼花图案 174

7.10 系统监控问题之一 175

7.11 系统监控问题之二 177

算法7.18 最小控制集的启发式算法 179

算法7.19 最小控制集的逻辑算法 179

习题七 179

第八章 网络及其应用 184

8.1 网络和网络流 184

8.2 最大流和最小割 186

8.3 应用——最大流问题 188

8.4 应用——最小代价流问题 192

算法8.2 最大流的双向调整法——Ford-Fulkerson算法 192

算法8.1 最大流的单向调整法 192

算法8.3 最小代价流的负回路算法 196

算法8.4 最小代价流的迭加算法 196

8.5 应用——开关网络 196

算法8.5 开关函数的单接触网络实现的算法 201

8.6 应用——网络计划技术 201

算法8.6 网络计划技术的算法 209

8.7 应用——前导网络 209

8.8 应用——非肯定型工程网络 215

算法8.8 前导网络时间参数计算法 215

算法8.7 工序网络时间参数计算法 215

算法8.9 非肯定型工程网络的算法 218

习题八 218

第九章 网络规划 225

9.1 网络规划 225

9.2 解的整数性 228

9.3 运输网络规划 230

算法9.3 位势法——解运输网络规划的单纯形法 237

9.4 分配网络规划 237

算法9.2 西北角法——求运输问题的初始基可行解 237

算法9.1 求运输表的闭回路的算法 237

算法9.4 匈牙利方法——解分配网络规划的互补松驰算法 243

9.5 转运网络规划 243

算法9.5 解转运网络规划的修正单纯形法 253

算法9.6 解转运网络规划的二阶段法 253

算法9.7 转运网络图上的原始-对偶算法 253

习题九 253

参考文献 262