第一章 图与子图 1
1.1 图与单图 1
1.2 图的同构 4
1.3 邻接矩阵和关联矩阵 13
1.4 子图 16
1.5 顶点的度 21
1.6 路和连通性 28
1.7 圈 34
1.8 最短路问题 38
1.9 Sperner引理 44
第二章 树 49
2.1 树 49
2.2 割边和键 54
2.3 割点 63
2.4 Cayley公式 65
2.5 连接问题 71
第三章 连通性 76
3.1 连通性 76
3.3 可靠通讯网络的构造 80
3.2 块 80
第四章 Euler游历和Hamilton圈 93
4.1 Euler游历 93
4.2 Hamilton圈 96
4.3 中国邮递员员问题 113
4.4 旅行售货员问题 116
第五章 匹配 118
5.1 匹配 118
5.2 2-部图的匹配和覆盖 123
5.3 完美匹配 129
5.4 人员工作分配问题 138
5.5 最优分配问题 139
第六章 边着色 144
6.1 边色数 144
6.2 Vizing定理 149
6.3 时间表问题 159
第七章 独立集和团 161
7.1 独立集 161
7.2 Ramsey定理 165
7.3 Turán定理 174
7.4 Schur定理 179
7.5 一个几何问题 182
第八章 顶点差色 185
8.1 色数 185
8.2 Bro′oks定理 193
8.3 Haj′os猜测 195
8.4 色多项式 198
8.5 围长和色数 205
8.6 存储问题 207
第九章 平面图 209
9.1 平面图和可平面图 209
9.2 对偶图 212
9.3 Euler公式 219
9.4 桥 223
9.5 Kuratowski定理 226
9.6 5-色定理和4-色猜测 228
9.7 非Hamilton可平面图 236
9.8 平面性算法 241
10.1 有向图 243
第十章 有向图 243
10.2 有向路 249
10.3 有向圈 254
10.4 工作排序问题 259
10.5 高效率计算机磁鼓的设计 261
10.6 单向道路系统的构造 262
10.7 比赛参加者的名次评定 264
11.1 流 268
第十一章 网络 268
11.2 截 272
11.3 最大流最小截定理 274
11.4 Menger定理 284
11.5 可行流 288
第十二章 圈空间和键空间 296
12.1 环流和势差 296
12.2 生成树的数目 300
12.3 完美正方形 305