第一章 引论 1
1 Konisberg桥问题(或Euler回路问题) 1
2 路径问题 2
3 应用举例 6
4 Hamilton回路问题 10
5 Ramsey问题 11
习题 12
第三章 基本概念 13
1 图的概念 13
2 同形 14
3 点与边的关联关系 15
4 道路与回路 17
5 Euler回路 17
6 Hamilton道路 19
7 图的矩阵表示法 22
2 例 24
8 道路矩阵 25
9 道路矩阵的Warshall算法 27
10 强连通概念与递归概念 29
习题 31
第三章 树 33
1 树的概念 33
3 基本性质 37
4 基本关联矩阵 40
5 树的数目 41
6 内向树与外向树 46
7 二元树 50
8 Huffman树 52
9 搜索树 55
10 DFS算法 56
11 旅行商问题 59
12 最佳匹配问题 62
习题 65
第四章 最佳路径问题 67
1 最佳路径问题 67
2 求最短路径的Dijkstra算法 68
3 最短树问题 70
4 最短树的Kruskal算法 72
5 求任意两点间的最短距离 73
6 求任意两点距离的Warshall算法 77
7 关键路径法 78
1 平面图 81
2 Euler公式 81
习题 81
第五章 平面图 81
3 极大平面图 82
4 Kuratowski图 83
5 Kuratowski定理 84
6 对偶图 88
7 五色问题 90
8 Minty引理 91
习题 92
第六章 电路网络 93
1 回路矩阵 93
2 回路矩阵的若干性质 95
3 基本关联矩阵Bk与基本回路矩阵C？的关系 97
4 割集矩阵 99
5 克希荷夫定律 103
6 电路问题 104
7 状态变量法理论基础 106
8 状态变量法 107
9 状态变量法举例 114
10 若干特殊性形 127
11 图论在电路中的其它应用 137
习题 144
第七章 图与代数方程组 145
1 矩阵的Cates图 145
2 代数方程组与Mason信号流图 146
3 图的运算 147
4 行列式的展开法 151
5 代数方程组的Coates解法 153
6 Mason公式 154
7 Mason公式的证明 158
习题 165
第八章 匹配理论 167
1 基本概念 167
2 关于匹配的基本定理 169
3 Hall定理 170
4 匈牙利算法与例 170
5 Konig定理 172
6 最佳匹配 173
7 最佳匹配的算法与例 177
习题 181
1 网络流问题与最大流 182
第九章 运输网络与开关网络 182
2 割切 183
3 Ford-Fulkerson最大流与最小割切定理 185
4 标号法 186
5 开关函数 190
6 传输矩阵与连接矩阵 191
7 简单接触网络的实现和算法 192
习题 200
第十章 图的算法 201
1 图的连通性判断 201
2 树的生成 202
3 Minty算法和Mayeda-Seshu算法 207
4 DFS算法的基本思想 212
5 无向图的DFS算法 213
6 有向图的DFS算法 215
7 图的块划分 216
8 强连通块的划分 220
第十一章 色数问题 225
1 问题的提出 225
3 独立集概念及其应用 227
4 求极大独立集的布尔代数算法 229
5 支配集 232
6 色数的一种求法 233
7 色数多项式 235
2 色数及其性质 236
8 应用举例 237
习题 238