网络优化

序言.i

前言iii

第1章 概论1

1.1 网络优化问题的例子1

1.2 图与网络2

1.2.1 有向图与网络的基本概念2

1.2.2 无向图与无向网络的基本概念5

1.3 图与网络的数据结构6

1.3.1 邻接矩阵表示法6

1.3.2 关联矩阵表示法7

1.3.3 弧表表示法7

1.3.4 邻接表表示法8

1.3.5 星形表示法8

1.4 计算复杂性的概念11

1.4.1 组合最优化问题11

1.4.2 多项式时间算法13

1.4.3 多项式问题16

练习题18

第2章 算法基础19

2.1 np,npc和np-hard概念19

.2.1.1 问题、实例与输入规模19

2.1.2 判定问题21

2.1.3 非确定多项式问题类(np)22

2.1.4 np完全问题类(npc)25

2.2 算法设计与分析29

2.2.1 贪婪算法30

2.2.2 动态规划31

2.2.3 线性规划方法——全幺模矩阵34

2.2.4 两分法36

2.2.5 网络搜索算法37

2.3 小结38

练习题38

第3章 最小树与最小树形图41

3.1 树的基本概念41

3.2 最小树算法44

3.2.1 kruskal算法44

3.2.2 prim算法46

3.2.3 sollin算法48

3.3 最小树形图49

3.4 最大分枝53

练习题56

第4章 最短路问题58

4.1 最短路问题的数学描述58

4.2 无圈网络与正费用网络：标号设定算法60

4.2.1 bellman方程60

4.2.2 无圈网络61

4.2.3 正费用网络..62

4.3 一般费用网络：标号修正算法65

4.3.1 bellman-ford算法65

4.3.2 一般的标号修正算法67

4.3.3 floyd-warshall算法68

练习题70

第5章 最大流问题73

5.1 最大流问题的数学描述73

5.1.1 网络中的流73

5.1.2 最大流问题76

5.1.3 增广路定理77

5.2 增广路算法79

5.2.1 ford-fulkerson标号算法79

5.2.2 残量网络81

5.2.3 最大容量增广路算法82

5.2.4 容量变尺度算法83

5.3 最短增广路算法83

5.3.1 距离标号84

5.3.2 最短增广路算法85

5.3.3 复杂度分析87

5.4 一般的预流推进算法88

5.4.1 一般的预流推进算法88

5.4.2 复杂度分析91

5.5 最高标号预流推进算法94

5.5.1 最高标号预流推进算法94

5.5.2 算法的复杂度分析94

5.6 单位容量网络上的最大流算法96

5.6.1 单位容量网络上的最大流算法97

5.6.2 单位容量简单网络上的最大流算法98

练习题98

第6章 最小费用流问题102

6.1 最小费用流问题的数学描述102

6.1.1 最小费用流问题102

6.1.2 最小费用流模型的特例及扩展104

6.2 消圈算法与最小费用路算法106

6.2.1 消圈算法106

6.2.2 最小费用路算法108

6.3 原始-对偶算法111

6.3.1 对偶问题及互补松弛条件111

6.3.2 原始-对偶算法112

6.4 瑕疵算法115

6.5 松弛算法122

6.6 网络单纯形算法127

6.6.1 算法的一般思路128

6.6.2 处理退化的方法131

6.6.3 初始的基本可行解133

6.6.4 容量有界的情形133

练习题136

第7章 匹配问题141

7.1 匹配问题的数学描述141

7.2 二部基数匹配问题144

7.2.1 增广路算法144

7.2.2 应用简单网络上的最大流算法147

7.3 非二部基数匹配问题147

7.4 二部赋权匹配问题151

7.5 非二部赋权匹配问题152

练习题162

索引及英文关键词165

参考文献...170