图论与网络最优化PDF电子书下载

第一章 基本概念 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