《网络最优化》求取 ⇩

第一章 基本概念1

1.1 集合和关系1

1.2 图3

1.3 关联关系8

1.4 子图11

1.5 连通性13

1.6 割集16

1.7 线性规划问题19

1.8 单纯形方法21

1.9 几何解释24

1.10 对偶理论27

习题一30

第二章 最小树和最小树形图32

2.1 引言32

2.2 树及其基本性质32

2.3 最小树及其基本性质37

2.4 求最小树的算法40

2.5 最小树的某些应用45

2.6 树形图及其基本性质48

2.7 求最小树形图的朱-刘算法50

2.8 求最大分枝的Edmonds算法57

2.9 最小树形图的某些应用61

习题二64

第三章 最短有向路67

3.1 引言67

3.2 最短有向路方程68

3.3 求最短有向路的代换法71

3.4 求最短有向路的Diikstra算法75

3.5 求最短有向路的逐次逼近法78

3.6 求最短有向路的线性规划法84

3.7 求所有点对间最短有向路的Floyd方法87

3.8 求所有点对间最短有向路的分解方法91

3.9 求m条最短有向路94

3.10 最短有向路的某些应用98

第四章 最大流106

4.1 引言106

4.2 基本最大流问题106

习题三108

4.3 最大流算法110

4.4 增最网络与流分解113

4.5 最大流算法的有效性分析117

4.6 求所有点对间的最大流124

4.7 最小费用流139

4.8 循环流151

4.9 最小费用循环流154

4.10 最大流的某些应用164

习题四170

5.2 对集174

第五章 最大对集174

5.1 引言174

5.3 二分图的对集180

5.4 二分图的最大基数对集185

5.5 二分网络的最大最小对集189

5.6 二分网络的最大权对集193

5.7 增广路，交错树和树花202

5.8 最大基数对集207

5.9 对偶定理215

5.10 最大权对集问题的线性规划表示219

5.11 最大权对集算法224

5.12 最大对集的某些应用232

习题五242

参考书目243

参考文献243