《图论与网络最优化》求取 ⇩

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