第一部分 集合论 1
第一章 集合 1
1.1 集合的概念及集合之间的关系 1
1.2 集合的运算 6
1.3 基本的集合恒等式 12
1.4 集合列的极限 20
习题一 25
第二章 二元关系 30
2.1 有序对与卡氏积 30
2.2 二元关系 35
2.3 关系矩阵和关系图 45
2.4 关系的性质 47
2.5 二元关系的幂运算 53
2.6 关系的闭包 56
2.7 等价关系和划分 65
2.8 序关系 72
习题二 79
第三章 函数 88
3.1 函数的基本概念 88
3.2 函数的性质 90
3.3 函数的合成 95
3.4 反函数 98
习题三 104
4.1 自然数的定义 108
第四章 自然数 108
4.2 传递集合 115
4.3 自然数的运算 118
4.4 N上的序关系 121
习题四 124
第五章 基数 126
5.1 集合的等势 126
5.2 有穷集合与无穷集合 129
5.3 基数 132
5.4 基数的比较 133
5.5 基数运算 139
习题五 147
第六章 序数 149
6.1 关于序关系的进一步讨论 149
6.2 超限递归定理 153
6.3 序数 157
6.4 关于基数的进一步讨论 166
习题六 168
第二部分 图论 173
第七章 图 173
7.1 图的基本概念 173
7.2 通路与回路 193
7.3 无向图的连通性 198
7.4 无向图的连通度 200
7.5 有向图的连通性 211
习题七 213
第八章 欧拉图与哈密尔顿图 216
8.1 欧拉图 216
8.2 哈密尔顿图 224
习题八 234
第九章 树 236
9.1 无向树的定义及性质 236
9.2 生成树 240
9.3 环路空间 246
9.4 断集空间 250
9.5 根树 253
习题九 256
第十章 图的矩阵表示 258
10.1 关联矩阵 258
10.2 邻接矩阵与相邻矩阵 264
习题十 270
第十一章 平面图 273
11.1 平面图的基本概念 273
11.2 欧拉公式 279
11.3 平面图的判断 283
11.4 平面图的对偶图 286
11.5 外平面图 290
11.6 平面图与哈密尔顿图 293
习题十一 297
第十二章 图的着色 299
12.1 点着色 299
12.2 色多项式 301
12.3 地图的着色与平面图的点着色 307
12.4 边着色 311
习题十二 315
第十三章 支配集、覆盖集、独立集与匹配 317
13.1 支配集、点覆盖集、点独立集 317
13.2 边覆盖集与匹配 322
13.3 二部图中的匹配 330
习题十三 333
第十四章 带权图及其应用 335
14.1 最短路径问题 335
14.2 关键路径问题 340
14.3 中国邮递员问题 343
14.4 最小生成树 348
14.5 最优树 355
14.6 货郎担问题 361
习题十四 368
参考书目 371
附录1 符号注释 372
附录2 名词与术语索引 375