第一章 引论

1 Konisberg桥问题(或Euler回路问题)

2 路径问题

3 应用举例

4 Hamilton回路问题

5 Ramsey问题

习题

第三章 基本概念

1 图的概念

2 同形

3 点与边的关联关系

4 道路与回路

5 Euler回路

6 Hamilton道路

7 图的矩阵表示法

2 例

8 道路矩阵

9 道路矩阵的Warshall算法

10 强连通概念与递归概念

习题

第三章 树

1 树的概念

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与基本回路矩阵C？的关系

4 割集矩阵

5 克希荷夫定律

6 电路问题

7 状态变量法理论基础

8 状态变量法

9 状态变量法举例

10 若干特殊性形

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

习题

第七章 图与代数方程组

1 矩阵的Cates图

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 问题的提出

3 独立集概念及其应用

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

5 支配集

6 色数的一种求法

7 色数多项式

2 色数及其性质

8 应用举例

习题