目录

第一章 引论

§1 K？nisberg桥问题（或Euler回路问题）

§2 路径问题

§3 应用举例

§4 Hamilton回路问题

§5 Ramsey问题

习题

第二章 基本概念

§1 图的概念

§2 同形

§3 点与边的关联关系

§5 Euler回路

§4 道路与回路

§6 Hamilton道路

§7 图的矩阵表示法

§8 道路矩阵

§9 道路矩阵的Warshall算法

§10 强连通概念与递归概念

习题

第三章 树

§1 树的概念

§2 例

§3 基本性质

§4 基本关联矩阵

§5 树的数目

§6 内向树与外向树

§7 二元树

§8 Huffman树

§9 搜索树

§10 DFS算法

§11 旅行商问题

§12 最佳匹配问题

习题

第四章 最佳路径问题

§1 最佳路径问题

§2 求最短路径的Dijkstra算法

§3 最短树问题

§4 最短树的Kruskal算法

§5 求任意两点间的最短距离

§6 求任意两点距离的Warshall算法

§7 关键路径法

习题

第五章 平面图

§1 平面图

§2 Euler公式

§3 极大平面图

§4 Kuratowski图

§5 Kuratowski定理

§6 对偶图

§7 五色问题

§8 Minty引理

习题

第六章 电路网络

§1 回路矩阵

§2 回路矩阵的若干性质

§3 基本关联矩阵Bk与基本回路矩阵Cf的关系

§4 割集矩阵

§5 克希荷夫定律

§6 电路问题

§7 状态变量法理论基础

§8 状态变量法

§9 状态变量法举例

§10 若干特殊情形

§11 图论在电路中的其它应用

习题

第七章 图与代数方程组

§1 矩阵的Coates图

§2 代数方程组与Mason信号流图

§3 图的运算

§4 行列式的展开法

§5 代数方程组的Coates解法

§6 Mason公式

§7 Mason公式的证明

习题

第八章 匹配理论

§1 基本概念

§2 关于匹配的基本定理

§3 Hall定理

§4 匈牙利算法与例

§5 Konig定理

§6 最佳匹配

§7 最佳匹配的算法与例

习题

第九章 运输网络与开关网络

§1 网络流问题与最大流

§2 割切

§3 Ford—Fulkerson最大流与最小割切定理

§4 标号法

§5 开关函数

§6 传输矩阵与连接矩阵

§7 简单接触网络的实现和算法

习题

第十章 图的算法

§1 图的连通性判断

§2 树的生成

§3 Minty算法和Mayeda-Seshu算法

§4 DFS算法的基本思想

§5 无向图的DFS算法

§6 有向图的DFS算法

§7 图的块划分

§8 强连通块的划分

第十一章 色数问题

§1 问题的提出

§2 色数及其性质

§3 独立集概念及其应用

§4 求极大独立集的布尔代数算法

§5 支配集

§6 色数的一种求法

§7 色数多项式

§8 应用举例

习题