第一章 图和子图 1
1.1 基本概念 1
1.2 子图及其运算 7
1.3 通路和回路 10
1.4 最短通路问题 13
1.5 子图集合的代数结构 17
1.6 关联矩阵与邻接矩阵 20
1.7 服务点设置问题 23
习题 28
第二章 树 34
2.1 定义和例子 34
2.2 树的基本特征 37
2.3 生成树 40
2.4 连接问题 44
习题 49
第三章 连通性 53
3.1 (点)连通度和边连通度 53
3.2 块 57
3.3 Menger 定理 61
3.4 极小 k—连通图 63
习题 65
第四章 边无关集和点独立集 67
4.1 边无关集(匹配) 67
4.2 二分图的边无关集 70
4.3 独立集和覆盖 72
4.4 Ramsey 数 77
习题 84
5.1 七桥问题与 Euler 图 88
第五章 E 图和 H 图 88
5.2 Hamilton 图 91
5.3 中国邮递员问题 100
5.4 旅行售货员问题 103
习题 106
第六章 图的染色 110
6.1 边染色 110
6.2 点染色 116
6.3 色多项式 122
习题 127
第七章 平面图 129
7.1 平面图和可平面图 129
7.2 Euler 公式 132
7.3 Kuratowski 定理 137
7.4 四色问题与五色定理 141
习题 144
第八章 有向图 146
8.1 有向图的概念 146
8.2 单向通路 148
8.3 单向回路 152
8.4 有向树与有序树 156
习题 162
第九章 网络最大流 165
9.1 网络的流与割 165
9.2 最大流最小割定理 170
9.3 标记法 173
习题 177
[附录] 数学竞赛中的图论问题 180
参考书目 201