第一章 基本概念 1
1几个实际问题 1
2图与子图 3
3顶点的度 7
4路、圈和连通 9
5有向图 14
6矩阵表示 18
7计算复杂性问题 19
第二章 树与树形图 23
1连通度 23
2割点、割边和块 26
3树及其基本性质 30
4最小树及其基本性质 35
5求最小树的算法 37
6树形图及其基本性质 41
7求最小树形图的算法 42
8可靠通讯网络的构造 45
第三章 最短路问题 50
1最短有向路方程 50
2求最短有向路的代换法 53
3求最短有向路的Dijkstra算法 56
4求所有点对间最短有向路的Floyd方法 59
5求所有点对间最短有向路的分解方法 61
6求m条最短有向路 64
7最短有向路问题的一些应用 66
第四章 分派问题 72
1对集 72
2二部的最大对集算法和Konig定理 77
3一般图的最大对集算法 84
4独立集和Ramsey数 93
5二部图的最大最小对集 100
6最优分派问题 102
第五章 邮递员问题和售货员问题 110
1 Euler环游 110
2中国邮递员问题 112
3 Hamilton圈 116
4 Hamilton回路 133
5旅行售货员问题及其应用 141
第六章 网络流问题 150
1基本概念和基本定理 150
2求最大流的算法 157
3相容性定理 165
4循环流 170
5最小费用流问题 173
6最小费用流算法 179
第七章 平面图 187
1图的可平面性 187
2对偶图 188
3 Doscartes—Euler公式 191
4 Kuratowski定理 193
5平面性算法 197
6厚度和交叉 201
第八章 应用实例 204
1选址问题 204
2统筹方法 208
3时间表问题 212
4车辆调度问题与启发式方法 216
5用网络流方法进行簿弱环节分析 220
参考文献 223
符号索引 237
名词索引 241