目录 1
第一章 引论 1
§1 K？nisberg桥问题（或Euler回路问题） 1
§2 路径问题 2
§3 应用举例 6
§4 Hamilton回路问题 10
§5 Ramsey问题 11
习题 12
第二章 基本概念 13
§1 图的概念 13
§2 同形 14
§3 点与边的关联关系 15
§5 Euler回路 17
§4 道路与回路 17
§6 Hamilton道路 19
§7 图的矩阵表示法 22
§8 道路矩阵 25
§9 道路矩阵的Warshall算法 27
§10 强连通概念与递归概念 29
习题 31
第三章 树 33
§1 树的概念 33
§2 例 34
§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
习题 80
第五章 平面图 81
§1 平面图 81
§2 Euler公式 81
§3 极大平面图 82
§4 Kuratowski图 83
§5 Kuratowski定理 84
§6 对偶图 88
§7 五色问题 90
§8 Minty引理 91
习题 92
第六章 电路网络 93
§1 回路矩阵 93
§2 回路矩阵的若干性质 95
§3 基本关联矩阵Bk与基本回路矩阵Cf的关系 97
§4 割集矩阵 99
§5 克希荷夫定律 103
§6 电路问题 104
§7 状态变量法理论基础 106
§8 状态变量法 107
§9 状态变量法举例 114
§10 若干特殊情形 127
§11 图论在电路中的其它应用 137
习题 144
第七章 图与代数方程组 145
§1 矩阵的Coates图 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
第九章 运输网络与开关网络 182
§1 网络流问题与最大流 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
§2 色数及其性质 226
§3 独立集概念及其应用 227
§4 求极大独立集的布尔代数算法 229
§5 支配集 232
§6 色数的一种求法 233
§7 色数多项式 235
§8 应用举例 237
习题 238