第一章 图的基本概念 1
1.1 图 1
1.2 子图 6
1.3 图的运算 13
1.4 图的同构 17
习题 18
第二章 路径、回路和割集 22
2.1 边序列、边列、路径和回路 22
2.2 连通图和非连通图 25
2.3 可分图和不可分图 27
2.4 E图和M图 29
2.5 最小化运算、回路集体和路径集体 35
2.6 中国邮递员问题 37
2.7 H图 40
2.8 旅行推销员问题 47
2.9 用分枝定界法解旅行推销员问题 49
2.10 割集 57
2.11 分离两个指定点的割集 65
习题 70
3.1 树及其性质 79
第三章 树 79
3.2 根树、二元树和生成树 86
3.3 树的编码 91
3.4 生成树的算法 94
3.5 最小生成树的算法 99
3.6 所有生成树的算法 103
3.7 基本回路和基本割集 109
3.8 边连通度和点连通度 112
3.91-同构和2-同构 117
习题 121
4.1 关联矩阵 126
第四章 图的短阵表示 126
4.2 回路矩阵 136
4.3 割集矩阵 144
4.4 邻接矩阵和路径矩阵 153
习题 163
第五章 平面图和对偶图 170
5.1 平面图 170
5.2 欧拉公式 174
5.3 平面性检测 177
5.4 对偶图 181
5.5自对偶图 190
5.6 厚度与交叉 195
习题 199
第六章 着色、匹配和覆盖 205
6.1 色数 205
6.2 独立集、支配集和色划分 207
6.3 计算色数的一种方法 214
6.4 着色多项式 215
6.5 匹配与最大匹配 219
6.6 覆盖 236
6.7 五色问题 240
习题 242
第七章 有向图 245
7.1 有向图的特性和类型 245
7.2 有向子图 246
7.3 有向欧拉图 248
7.4 有向树 251
7.5 有向图的关联矩阵、回路矩阵和割集矩阵 262
7.6 生成树的计数 272
7.7 有向图的邻接矩阵 274
7.8 有向图中的H回路 282
7.9 非循环有向图及最小消环法 289
习题 295
第八章 图论在开关网络中的应用 298
8.1 开关函数 298
8.2 开关网络分析 299
8.3 开关网络综合 303
8.4 割集矩阵的可实现性 310
8.5 SP网络 313
习题 316
9.1 具有独立源的RLC网络分析 319
第九章 图论在电网络分析中的应用 319
9.2 有源网络的拓扑分析 331
习题 341
第十章 图论在运筹学中的应用 345
10.1 最短路径问题 345
10.2 运输网络 361
10.3 最小费用流 371
10.4 工程规划中的任务网络 374
习题 384
参考文献 388