离散数学引论PDF电子书下载

第一篇 图及其算法 1

1.1 什么是图论 1

1.2 图的定义 7

1.3 Brouwer不动点定理 12

1.4 Dijkstra算法 14

习题一 17

1.5 树 22

1.6 生成树 26

1.6.1 生成树的个数 26

1.6.2 最优生成树的Kruskal算法 28

1.7 常用树 30

1.7.1 有序二元树 30

1.7.2 HuffmanA树 32

习题二 35

1.8 平面图 37

1.8.1 平面图及其Euler公式 37

1.8.2 对偶图和极大平面图 43

1.8.3 Kuratowsky定理 44

1.8.4 图的厚度 46

习题三 47

1.9 纵深搜索与平面嵌入算法 49

1.9.1 广度优先与深度优先搜索算法 49

1.9.2 求割顶和块的算法 52

1.9.3 有向图的DFS和极大强连通子图的算法 54

1.9.4 平面嵌入算法 56

习题四 63

1.10 匹配 64

1.10.1 匹配理论 65

1.10.2 二分图中最大匹配与最佳匹配的算法 72

习题五 76

1.11 图上遍历 78

1.11.1 Euler图 78

1.11.2 求Euler回路的算法 81

1.11.3 中国邮路问题 82

1.11.4 Harnilton图 84

习题六 91

1.12 色 92

1.12.1 边色数 93

1.12.2 顶色数与面色数 96

1.12.3 色多项式 99

习题七 103

1.13 支配集、独立集和Ramsey数 105

1.13.1 支配集和独立集 105

1.13.2 a（G），b（G），r（G）的计算 106

1.13.3 Ramsey数 110

1.13.4 多元Ramsey数和Schur定理 116

习题八 116

1.14 有向图 118

1.14.1 有向图的连通性 118

1.14.2 有向轨与竞赛图 119

1.14.3 有向圈与竞赛图 122

1.14.4 有向Euler图 125

习题九 129

1.15 网络流 130

1.15.1 Ford-Fulkerson最大流算法 130

1.15.2 Dinic最大流算法 133

1.15.3 有上下界的网络中的流 138

1.15.4 有供需约束的流 142

1.15.5 RERT问题 143

1.15.6 流与二分图 146

习题十 148

1.16 连通度 153

1.16.1 无向图的顶连通度 153

1.16.2 有向图的顶连通度 156

1.16.3 无向图的边连通度 157

1.16.4 有向图的边连通度和弱独立外向生成树 158

1.16.5 可靠通讯网络 160

习题十一 162

2.1 什么是组合论 166

第二篇 组合基础 166

2.2 鸽笼原理 169

2.3 ＋ ×原理与排列组合 172

2.3.1 无重复的排列组合 173

2.3.2 Catalan数 174

2.3.3 可重复的排列组合 178

习题一 182

2.4 容斥原理 184

习题二 192

2.5 生成函数 193

2.5.1 生成函数概念 193

2.5.2 组合数的生成函数 194

2.5.3 拆分自然数 196

2.5.4 排列数的生成函数 199

习题三 202

2.6 递归方程 204

2.6.1 递归方程的初值问题 204

2.6.2 线性常系数递归方程的生成函数解法 205

2.6.3 常系数线性齐次递归方程的特征值解法 208

2.6.4 常系数线性非齐次递归方程的解 212

2.6.5 递归方程的其它解法 212

2.6.6 Stirling数 215

习题四 216

第三篇 代数与计数 219

3.1 代数系统及其性质 219

3.1.1 代数系统的定义 219

3.1.2 代数系统的同构与同态 221

3.2 群、环、域 225

3.2.1 群 225

3.2.2 环 227

3.2.3 域 228

习题一 230

3.3.1 置换 233

3.3 置换群和循环群 233

3.3.2 置换群与循环群 237

3.4 Lagrange定理和Burnside定理 243

3.5 Polya定理 247

习题二 252

3.6 图的群 253

3.6.1 图的自同构群 253

3.6.2 有限群的Cayley图 259

习题三 264

4.1.1 圈空间 266

4.1 圈空间和断集空间 266

第四篇 离散数学中的空间,矩阵和拟阵 266

4.1.2 断集空间 269

4.2 关联矩阵和邻接矩阵 272

4.2.1 关联矩阵 272

4.2.2 邻接矩阵 279

4.3 圈矩阵和割集矩阵 286

4.4 开关网络分析 292

习题一 299

4.5.1 拟阵的概念 303

4.5 拟阵 303

4.5.2 拟阵理论 308

习题二 312

4.6 倒称矩阵与层次分析 314

4.7 正交拉丁方 322

4.8 区组设计与区组矩阵 327

4.8.1 BIBD问题 328

4.8.2 区组关联矩阵 328

4.8.3 Hadamard矩阵 331

4.8.4 区组设计的构作 333

4.9 魔矩阵密码 336

习题三 342

第五篇 不确定Turing机和计算的时间复杂度 344

5.1 好算法和坏算法 344

5.2 确定Turing机和NP类问题 346

5.3 NPC问题和Cook定理 350

5.4 NPC中的组合问题 356

5.5 NPC中的图论问题 360

习题 376

第六篇 数理逻辑 380

6.1.2 联结词与命题公式 381

6.1 命题逻辑 381

6.1.1 命题及其真假 381

6.1.3 真值表 382

6.1.4 等价公式、代换定理与对偶定理 385

6.1.5 范式 387

6.2 命题逻辑中的推理 390

6.2.1 蕴含关系 390

6.2.2 真值表推理法 391

6.2.3 直接推理法 392

习题一 393

6.2.4 间接推理法 393

6.3 谓词逻辑 395

6.3.1 命题的谓词表达形式 395

6.3.2 量词 396

6.3.3 谓词公式及其变元 397

6.3.4 谓词逻辑中的等价定律、代入规则 399

6.4 谓词逻辑中的推理 403

习题二 406

参考文献 409