离散数学 第2分册：集合论与图论PDF电子书下载

第一部分 集合论 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