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