第一篇 图论 1
第一章 基本概念 1
1.1 基本定义 1
1.2 子图和补图 3
1.3 通道、轨迹、路径和回路 5
1.4 图的连通性和片 7
1.5 图的运算 8
1.6 特殊图 11
1.7 割点和可分图 13
1.8 同构和2-同构 14
1.9 进一步阅读 17
1.10 习题 17
1.11 参考文献 19
第二章 树、割集和回路 20
2.1 树、生成树和补生成树 20
2.2 K-树、K-生成树和林 25
2.3 秩和零度 27
2.4 基本回路 27
2.5 割集 28
2.6 切割 29
2.7 基本割集 31
2.8 生成树、回路和割集 32
2.9 进一步阅读 34
2.10 习题 34
2.11 参考文献 36
第三章 欧拉图和哈密顿图 37
3.1 欧拉图 38
3.2 哈密顿图 42
3.4 习题 46
3.2 进一步阅读 46
3.5 参考文献 47
第四章 图和矢量空间 49
4.1 群和域 49
4.2 矢量空间 51
4.3 图的矢量空间 54
4.4 回路和割集子空间的维数 58
4.5 回路和割集子空间的关系 60
4.6 回路和割集子空间的正交性 61
4.8 习题 63
4.7 进一步阅读 63
4.9 参考文献 64
第五章 有向图 65
5.1 基本定义和概念 65
5.2 图和关系 69
5.3 有向树或单向树 70
5.4 有向欧拉图 73
5.5 有向生成树和有向欧拉轨迹 75
5.6 有向哈密顿图 77
5.7 无圈有向图 79
5.8 比赛图 80
5.9 进一上阅读 81
5.10 习题 81
5.11 参考文献 82
第六章 图的矩阵 84
6.1 关联矩阵 84
6.2 切割矩阵 86
6.3 回路矩阵 89
6.4 正交关系 91
6.5 切割、关联和回路矩阵的子矩阵 92
6.6 单位模矩阵 96
6.7 生成树的数目 98
6.8 生成2-树的数目 101
6.9 有向图中有向生成树的数目 103
6.10 邻接矩阵 106
6.11 考茨(Coates)图和梅森(Mason)图 109
6.12 进一上阅读 116
6.13 习题 116
6.14 参考文献 118
7.1 平面图 120
第七章 平面性和对偶性 120
7.2 欧拉公式 122
7.3 Kuratowski定理和平面性的另一些特征 124
7.4 对偶图 126
7.5 平面性和对偶性 129
7.6 进一步阅读 131
7.7 习题 131
7.8 参考文献 132
第八章 连通度和匹配 134
8.1 连通度或顶点连通度 134
8.2 边连通度 138
8.3 规定度的图 139
8.4 Menger定理 142
8.5 匹配 144
8.6 二分图中的匹配 145
8.7 一般图中的匹配 150
8.8 进一步阅读 155
8.9 习题 155
8.10 参考文献 157
第九章 覆盖和着色 159
9.1 独立集和顶点覆盖 159
9.2 边覆盖 164
9.3 边着色和色指数 165
9.4 顶点着色和色数 169
9.5 色多顶式 171
9.6 四色问题 173
9.7 进一步阅读 174
9.8 习题 175
9.9 参考文献 176
第十章 拟阵 179
10.1 基本定义 179
10.2 基本性质 181
10.3 等价公理系统 184
10.4 拟阵的对偶性和拟图 186
10.5 约束、收缩和拟阵的子式 191
10.6 拟阵的可表达性 193
10.7 二元拟阵 194
10.8 可定向拟阵 197
10.9 拟阵和Greedy算法 199
10.10 进一步阅读 201
10.11 习题 202
10.12 参考文献 204
第二篇 电网络理论 207
第十一章 图和网络 207
11.1 回路和割集变换 208
11.2 回路和割集系统方程组 211
11.3 混合-变量法 216
11.4 图的主划分 218
11.5 状态方程 223
11.6 电阻网络的无增益特性 228
11.7 进一步阅读 229
11.8 习题 229
11.9 参考文献 231
12.1 引言 234
第十二章 N端口电阻网络 234
12.2 秩为n的n端口电阻网络的Y矩阵 240
12.3 (n+1)节点n端口电阻网络的实现-I 249
12.4 割集和回路矩阵的实现 254
12.5 (n+1)节点n端口电阻网络的实现-II 263
12.6 进一步阅读 268
12.7 习题 268
12.8 参考文献 270
13.1 无互感RLC网络的拓扑公式 273
第十三章 网络函数和网络灵敏度 273
13.2 一般线性网络的拓扑公式 278
13.3 伴随网络和网络灵敏度的计算 284
13.4 进一步阅读 290
13.5 习题 291
13.6 参考文献 291
第三篇 算法图论 293
第十四章 算法分析 293
14.1 传递闭包 294
14.2 传递定向 299
14.3 深度优先搜索 308
14.4 2-连通性与强连通性 313
14.5 程序图的简化 319
14.6 程序图的控主 325
14.7 进一步阅读 332
14.8 习题 333
14.9 参考文献 334
第十五章 算法优化 338
15.1 最短路径 338
15.2 最小加权路径长度树 344
15.3 最优二元搜索树 351
15.4 图的最大匹配 355
15.5 二分图中的最大匹配 363
15.6 完美匹配、最优分配和时间表的安排 369
15.7 运输网络中的流 375
15.8 最优分支 388
15.9 进一步阅读 392
15.10 习题 393
15.11 参考文献 394
名词索引 401