《图和网络及其应用》求取 ⇩

算法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