前言 1
第一章 基本概念 3
1 图 3
2 有向图与无向图 4
3 图的顶与边(弧) 5
4 1—图 5
5 平面图与非平面图 6
6 顶点次数 7
7 部分图与子图 8
8 图的矩阵表示 9
9 链与圈，路与回路 11
10 图的同构 13
习题 14
1 树 19
第二章 树与树形图 19
2 跨顶树 21
3 树形图 24
4 联接图上的最短路 28
习题 36
第三章 ？和？维数 40
1 尤拉圈 40
2 环和 44
3 余圈 45
4 向量空间 49
5 圈维数 50
6 圈的矩阵表示 53
7 数树 58
习题 68
2 平面图的面 72
1 测地变换 72
第四章 平面图 72
3 尤拉公式 74
4 对偶图 78
5 库拉图斯基定理 80
6 库拉图斯基定理充分性的证明 82
习题 86
第五章 两分图(偶图) 89
1 基本概念与基本定理 89
2 两分图的矩阵表示 92
3 两分图的并列集 99
习题 101
第六章 网络上的流 103
1 网络 103
2 流量的调整 106
3 极大流量——极小截量定理 109
4 极大流量——极小截量定理的简单应用 113
5 供求定理 116
6 对称的供求定理 119
7 环流问题 124
8 环流与势差 130
习题 136
第七章 网络流理论在图论上的应用(具已知半次的图的存在性) 143
1 蒙格尔定理 143
2 具已知半次的 p——图的存在性 146
3 具已知半次的对称 p——图的存在性 151
4 具已知半次的无环 p——图的存在性 154
5 具已知半次的竞赛图的存在性 160
习题 163
1 断集、断量与断量的基本性质 167
第八章 图的联接性 167
2 集块 173
3 蒙格尔定理在图的联接性上的应用 176
4 断量与边数 181
5 极小2——联图的结构 185
6 3——联图的结构 193
习题 200
第九章 尤拉圈与哈密尔顿图 203
1 尤拉圈 203
2 哈密尔顿问题 204
3 图成 H——型的充分条件 206
4 图成 H——型的必要条件 217
5 有向图的哈密尔顿回路 223
6 哈密尔顿链与哈密尔顿路 231
7 竞赛图上 H——路的求法 237
习题 244
第十章 并列集(对集) 248
1 极大并列集 248
2 极小覆盖 253
3 两分图上的极大并列集 255
4 两分图上顶点的配对 257
5 最优安排问题 262
6 完美并列集 266
习题 276
第十一章 稳固集(独立集) 280
1 稳固集与径集 280
2 极大稳固集 281
3 涂兰定理及其有关问题 288
习题 295
1 着色指数 298
第十二章 图的着色 298
(一)边的着色 298
2 图的分类 313
3 边临界图 318
(二)点的着色 319
1 图的色数 319
2 临界图 327
3 着色多项式 333
4 平面图的可——5着色 337
习题 339
第十三章 拉姆绥定理与拉姆绥数 344
1 拉姆绥定理 344
2 拉姆绥定理的应用 349
3 拉姆绥定理在图论上的应用 352
4 N(3，3，3，…，3；2)?的确定 359
习题 362
第十四章 超图 364
1 基本概念 364
2 超图的链和圈 367
3 超图的代表图 371
4 超图的并列集 375
5 超图的径集 376
6 超图的着色 385
7 超图的集团 390
8 平衡超图 393
习题 405
参考书目 408
名词索引 408