第一章 图论 1
第一节 图论简史 1
第二节 图的一般知识 3
1.图的概念 3
2.图论的基本术语 4
3.子图 7
第三节 树 8
1.树的概念 8
2.树的性质 9
3.图的部分树 10
4.图的部分树的求法 11
5.最小部分树 12
6.最小部分树的求法 13
第二章 网络分析 16
第一节 最短路 16
1.有向图 16
2.最短路的Dijkstra算法 17
3.最短路的矩阵算法 25
4.最短路的Bellman算法 30
第二节 网络最大流 33
1.流的概念 33
2.网络流中的若干基本概念 34
3.Ford-Fulkersom标号法 38
4.最大流的验证 44
5.匹配问题--网络最大流的一个应用 49
第三节 最大流的费用优化问题 52
1.最优费用最大流的概念 52
2.最优费用增广链及其求法 53
第三章 网络计划技术及其应用 62
第一节 绪论 62
第二节 网络图的概念 64
1.网络图的组成 64
2.网络图的画法规则 67
第三节 网络图中的时间参数 74
1.作业时间的计算 75
2.事项时间的计算 81
3.工序时间的计算 84
4.时差与关键线路 87
1.图上算法 90
第四节 网络计划中的计算法 90
2.表上算法 91
3.矩阵算法 91
第五节 最优网络计划的制定 96
1.工期--成本优化 96
2.工期--资源优化 103
第四章 实用网络计算中的一些计算机程序 110
1.算法思想 112
第一节 求无向图中最小部分树程序 112
2.框图 115
3.程序清单 116
4.使用说明 117
5.运算实例 117
第二节 求赋权图中最短路程序 119
1.求有向图中给定节点到另一给定节点间的最短路及其路权程序 119
2.求有向图中给定节点到其余所有节点间的最短路及其路权程序 124
3.求无向图中所有节点对之间的最路短权程序 131
4.求带负弧权的有向图中给定节点到其余各节点之间的最短路及其路权程序 134
第三节 求网络最大流程序 139
1.算法思想 139
2.框图 141
3.程序清单 142
4.使用说明 143
5.运算实例 144
第四节 求网络图中最优费用最大流程序 145
1.算法思想 145
2.框图 146
3.程序清单 150
4.使用说明 153
5.运算实例 154
第五节 PERT程序 155
1.算法思想 155
2.框图 156
3.程序清单 157
4.使用说明 158
5.运算实例 159
附录 网络应用图例 161