《管理的图论方法》

第一章引论1

第一节　图论的由来、发展与意义1

第二节　图与数学模型2

第三节　关于本书的几点说明4

第二章　图的基本概念6

第一节　图的直观概念6

第二节　与集合有关的符号表示7

第三节　图的抽象概念8

第四节　几种常用的图10

第五节　图的运算13

第六节　道路，回路和连通图14

第七节　图的矩阵表示16

第三章　计划评审法19

第一节　计划评审法的基本概念19

第二节　计划评审法的适用范围20

第三节　计划评审法的特点20

第四节　计划评审法的基本步骤21

第五节　计划评审法中活动时间的推断27

第六节　控制与资源分派29

第七节　计划评审法网络图的另一种形式30

第一节　树的概念33

第四章　树与二元树33

第二节　树的基本特性37

第三节　二元树38

第四节　最优二元树（Huffman树）42

第五章　具有实物形态的网络算法48

第一节　关于算法48

第二节　求最短道路的Dijkstra算法49

第三节　求最短树的Kruskal算法56

第六章　Euler图59

第一节　Euler图的概念59

第二节　中国邮路问题60

第一节　Hamilton图的概念64

第七章　Hamilton图64

第二节　旅行商人问题68

第八章　网络流图与最大流71

第一节　网络流图与最大流的概念71

第二节　割切72

第三节　最大流最小割切定理74

第四节　标号算法75

第五节　Dinic算法78

第六节　容量有上下界的网络82

第七节　多发点、多收点的网络和有供需约束的流84

第一节　几个实例87

第九章　动态的网络—Petri网87

第二节　Petri网的概念91

第十章　搜索树与先深搜索法94

第一节　搜索树94

第二节　先深搜索法的意义95

第三节　先深搜索算法98

第十一章　分支定界法102

第一节　分支定界法102

第二节　用分支定界法解决最短工期问题104

第三节　用分支定界法解决最低旅费问题107

第四节　用分支定界法解决最优匹配问题111

第一节　匹配114

第十二章　二分图的匹配114

第二节　二分图的匹配116

第三节　人员安排问题117

第四节　最优分派问题119

第十三章　覆盖集、独立集和支配集123

第一节　覆盖集123

第二节　支配集124

第三节　独立集125

第四节　覆盖集，独立集和支配集之间的关系127

第五节　支配数与覆盖数的算法128

第一节　边着色131

第十四章　着色问题131

第二节　二分图的边着色132

第三节　顶点着色136

第四节　面着色139

第十五章　有向图141

第一节　有向图的概念141

第二节　工作顺序排列问题142

第三节　构造单向道路系统145

附录　本书中有关算法的C-语言程序147

1　求PERT图的关键道路算法147

2　求最短道路的Dijkstra算法149

3　求最小生成树Kruskal算法151

4　求最大流的标号算法154

5　求最大流的Dinic算法156

6　先深搜索算法159

7　求最大匹配的Hungarian算法162

8　求最优匹配的Kuhn—Munkres算法166

9　顶点着色算法175

10　强连通图的构造算法178

11　栈操作和队列操作180

主要参考资料184