《网络最优化》

第一章最优化及最优化算法1

1 非线性规划与线性规划1

2 组合最优化问题5

3 问题与算法10

4 算法的复杂性14

习题17

第二章图与网络19

1 图与图论19

2 无向图与有向图24

3 图的子图与图的收缩28

4 图的连通性与图的割集31

5 几类重要的图和网络34

习题38

第三章最小树与 Gteedy 算法40

1 树及其基本性质40

2 最小树及其基本性质42

3 求最小树的 Dijkstra 算法46

4 求最小树的 Kruskal 算法47

5 Greedy 算法及其应用49

习题51

第四章最短路与标号法52

1 解最短路问题的 Dijkstra 算法52

2 Dijkstra 算法的应用57

3 组合算法中的标号方法60

4 求所有点对间最短路的 Floyd 算法63

5 检测有向网络中是否有负圈的方法69

习题71

第五章最小树形图73

1 树形图及其基本性质73

2 广探法与深探法77

3 求渠道图的最小树形图的算法80

4 求最小树形图的朱—刘算法85

5 Edmonds 的最大分枝算法95

习题98

第六章最大流与增广路101

1 最大流问题101

2 最大流算法107

3 增量网络与分层增量网络110

4 最大流算法的改进114

5 最小费用流问题119

习题127

第七章最优匹配与交错路128

1 图的匹配128

2 交错路算法与二分图最大基数匹配133

3 二分网络最大权匹配137

4 一般图上的匹配与中国邮递员问题145

习题150

第八章NP 完全问题152

1 NP 问题与 NP 完全问题152

2 近似算法157

3 旅行售货员问题166

习题169

参考书目170

参考文献171