第一章 绪论 1
1.1 图的图形描述 1
1.2 图的拓扑变换 3
1.3 图的计算复杂性 4
习题与思考题 7
第二章 图的基本概念 9
2.1 图与子图 9
2.2 图的连通性 14
2.3 图的矩阵表示 19
2.4 图在计算机里的存贮 32
2.5 图的遍历 34
习题与思考题 39
第三章 树与割集 44
3.1 无向树 44
3.2 生成树 46
3.3 有向树 52
3.4 有向树的应用 55
3.5 树的存贮结构 60
3.6 树的遍历 64
3.7 图的中心和中位点 67
3.8 图的块划分 70
3.9 割集 82
3.10 基本割集 88
习题与思考题 92
第四章 平面图 97
4.1 可平面图的概念 97
4.2 平面图的性质 99
4.3 平面图的判别 101
4.4 平面性算法 106
4.5 图的交叉和厚度 112
4.6 对偶图 114
习题与思考题 120
第五章 偶图与匹配问题 124
5.1 偶图的定义及性质 124
5.2 匹配的概念 126
5.3 偶图的完全匹配 128
5.4 偶图的最大权匹配 134
5.5 一般图的最大基数匹配 142
5.6 一般图的最大权匹配 148
习题与思考题 155
第六章 图的着色 158
6.1 地图的着色 158
6.2 五色定理 159
6.3 边的着色 161
6.4 独立集、支配集、覆盖和团 165
6.5 点的着色 172
6.6 着色多项式 176
习题与思考题 179
7.1 从指定点到其他点的最短路径 183
第七章 路径问题 183
7.2 任意两点间的最短路径 186
7.3 最优路径 193
7.4 关键路径 197
习题与思考题 200
第八章 回路问题 203
8.1 E图和M图 203
8.2 欧拉图的寻迹 207
8.3 中国邮路问题 211
8.4 有向欧拉图 215
8.5 H图 221
8.6 有向H图 228
8.7 H图的寻迹 230
8.8 货郎担问题 234
8.9 货郎担问题的近似解法 236
8.10 用分技定界法解货郎担问题 241
习题与思考题 247
第九章 网络的流 251
9.1 流与切割 251
9.2 最大流最小切割定理 254
9.3 标记法 257
9.4 最短路径法 260
9.5 最大流最小切割定理的应用推广 265
9.6 最小费用流 267
9.7 有向图的中国邮路问题 273
9.8 无向网络的流 275
习题与思考题 281
符号表 283
参考文献 284