网络最优化PDF电子书下载

第一章 最优化及最优化算法 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