1.1 线图及其子图 1
第一章 无向图 1
1.2 通路和回路 9
1.3 E 图和 M 图 14
4.5 边权网络的流可靠度 18
4.6 点权网络 19
1.4 不可分图 23
1.5 最小化运算和环积运算 29
1.6 树 38
1.7 关联集和关联矩阵 46
1.8 回路矩阵 55
1.9 割集和割集矩阵 65
习题 81
第二章 有向图 85
2.1 有向图及其各种矩阵 85
2.2 单向子图 103
习题 111
第三章 平面图 114
3.1 线图的同构与二同构 114
3.2 平面图 122
3.3 对偶 129
3.4 平面性的判定 135
习题 142
第四章 网络流 145
4.1 分离两个指定顶点的割集 145
4.2 边权网络中的最大流最小割定理 151
4.3 网络流算法 162
4.4 无向边权网络 173
4.7 点割与点半割的生成 205
习题 213
5.1 对集、覆盖及独立集 219
第五章 对集 219
5.2 二分图中的最大对集、完全对集及完美对集 224
5.3 匈牙利方法 232
5.4 库恩-曼克莱斯(Kuhn-Munkres)算法 237
习题 244
第六章 连通性 248
6.1 连通度和边连通度 248
6.2 门格尔(Menger)的一组定理 250
6.3 用矩阵研究连通性 256
6.4 找单向通路和单向回路的一个方法 263
6.5 在社会科学中的应用 267
习题 270
第七章 电网络的拓扑分析 272
7.1 电网络方程 273
7.2 无源网络的网络函数 291
7.3 有源网络的网络函数 301
7.4 树的生成 319
习题 343
第八章 图论在计算机科学中及其它方面的应用 347
8.1 单向树 348
8.2 有序树 352
8.3 霍夫曼(Huffman)树 358
8.4 用图论方法安排数据存放 361
8.5 用线图结构处理数据管理系统 369
8.6 流图 381
8.7 开关网络分析 386
8.8 复杂系统的可靠度计算 393
习题 400
1 集合和集合的运算 402
附录Ⅰ 预备知识 402
2 行列式 406
3 矩阵 413
4 群和域 425
5 线性空间 430
附录Ⅱ 一组图论程序 433
1 求线图中所有两顶点间的最短通路值 433
2 求线图中若干顶点对间的最短通路 434
3 求线图中一定点到各顶点间的最短通路 437
4 求线图中两定点间的最短通路 440
5 求无向图的最优树 445
6 求无向连通图的一棵树 447
7 求无向图的森林 448
8 求二分图的最大对集 450
9 求赋权完全二分图的最优对集 454
10 求无向连通图的基本回路集 461
11 求无向连通图的基本割集组 463
12 求网络的最大流 466
参考文献 469
名词索引 470