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