第一章 引论 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