1 图形与部分图形 1
1.1 图形与简单图形 1
1.2 图形同构 5
1.3 接合与相邻矩阵 10
1.4 部分图形 11
1.5 顶点价数 14
1.6 路线与连通 16
1.7 循环 20
应用 22
1.8 最短路线问题 22
1.9 Sperner引理 30
2 树 34
2.1 树 34
2.2 割边与键 37
2.3 割顶点 42
2.4 Cayley公式 44
应用 49
2.5 连通管问题 49
3 连通数 57
3.1 连通数 57
3.2 块形 60
3.3 建造实用的通信网路 65
应用 65
4 Euler环游与Hamilton循环 69
4.1 Euler环游 69
4.2 Hamilton循环 72
应用 84
4.3 中国邮差问题 84
4.4 旅行推销员问题 88
5 配对 93
5.1 配对 93
5.2 二裂图形的配对与覆盖 96
5.3 完备配对 102
5.4 人员分派问题 107
应用 107
5.5 最佳分派问题 113
6 边着色 120
6.1 边色彩数 120
6.2 Vizing定理 124
应用 128
6.3 时刻表问题 128
7 独立集合与结块 134
7.1 独立集合 134
7.2 Ramsey定理 137
7.3 Tur'an定理 145
7.4 Schur定理 149
应用 149
7.5 一个几何问题 151
8 顶点着色 156
8.1 色彩数 156
8.2 Brooks定理 163
8.3 Haj？s推测 165
8.4 色彩多项式 167
8.5 腰长与色彩数 173
应用 175
8.6 一个仓库问题 175
9.1 平面与可平面化图形 180
9 可平面化图形 180
9.2 对偶图形 185
9.3 Euler公式 190
9.4 桥 194
9.5 Kuratowski定理 201
9.6 五色定理与四色推测 207
9.7 非Hamilton可平面化图形 213
应用 216
9.8 一种平面化的算法 217
10 有向图形 225
10.1 有向图形 225
10.2 有向路线 229
10.3 有向循环 233
应用 238
10.4 一个工作序列问题 238
10.5 设计一个有效的电算鼓 240
10.6 建造一个单行道的道路系统 243
10.7 评审参加比赛者的等级 245
11 网路 252
11.1 流程 252
11.2 割 256
11.3 极大流程极小割定理 259
应用 267
11.4 Menger定理 267
11.5 可行流程 272
12 循环空间与键空间 279
12.1 环流与位差 279
12.2 张成树的个数 287
应用 290
12.3 完备正方形 290
附录Ⅰ 星号习题提示 298
附录Ⅱ 四个图形及其各种性质表 306
附录Ⅲ 有趣的图形 308
附录Ⅳ 未解决的问题 321
附录Ⅴ 进一步阅读的资料 336
符号总汇 338
索引 343