1 通论
1.1 图论的内容与历史回顾
1.2 图的定义
1.3 轨道与连通
1.4 Brouwer不动点定理
1.5 Dijkstra算法
习题
2 树
2.1 树及其性质
2.2 生成树的个数
2.3 Kruskal算法
2.4 几类常用树
习题
3 连通性
3.1 连通性和Whitney定理
3.2 割顶、桥、块
3.3 可靠通讯网的构作
习题
4 可行遍性
4.1 Euler图
4.2 中国邮路问题
4.3 Hamilton图
4.4 货郎问题
习题
5 平面图
5.1 平面图的概念
5.2 Euler公式
5.3 平面图的对偶图
5.4 Kuratowsky定理
5.5 图的厚度
习题
6 纵深搜索算法与平面嵌入算法
6.1 广度与深度优先搜索法
6.2 平面嵌入算法
习题
7 匹配理论及其应用
7.1 匹配与许配
7.2 匹配基本定理
7.3 二分图中最大匹配与最佳匹配的算法
习题
8 支配集与独立集
8.1 支配集与独立集的概念
8.2 支配集、覆盖数和独立数的计算
8.3 支配集与独立集的应用
8.4 Ramsey数r(k,l)
习题
9 着色理论
9.1 边色数
9.2 Ramsey数和Schur定理
9.3 时间表问题
9.4 顶色数
9.5 面色数
9.6 颜色多项式
9.7 求色数的一个算法
习题
10 有向图
10.1 有向图的连通性
10.2 有向Euler图
10.3 有向轨
10.4 有向圈
习题
11 网络中的最大流
11.1 Ford和Fulkerson算法
11.2 Dinic算法
11.3 容量有上下界的网络
11.4 有供需约束的流
习题
12 网络流方法的应用
12.1 顶连通度
12.2 有向图的连通度和无向图的边连通度
12.3 有向图的边连通度和弱独立外向生成树
12.4 二分图
12.5 关于PERT的两个问题
习题
13 无向图中的空间与矩阵
13.1 圈空间
13.2 断集空间
13.3 关联矩阵
13.4 圈矩阵
13.5 割集矩阵
13.6 邻接矩阵与道路矩阵
13.7 开关网络
习题
14 有向图中的矩阵
14.1 邻接矩阵与道路矩阵
14.2 关联矩阵和生成树的数目
14.3 圈矩阵与割集矩阵
14.4 电路网络
习题
15 NPC概念与Cook定理
15.1 算法的好与坏
15.2 判定问题的NP类
15.3 NPC与Cook定理
15.4 NPC中的几人组合问题
习题
16 NPC中若干著名的图论问题
16.1 团、独立集和顶覆盖
16.2 Hamilton轨和Hamilton圈
16.3 图的色数
16.4 有向图的反馈集
16.5 Steiner树
16.6 最大断集
16.7 图的直线排列
16.8 多商品整流问题
习题
17 拟阵与图
17.1 定义与例
17.2 拟阵与图论
习题
习题答案或提示
参考文献