离散数学引论PDF|Epub|txt|kindle电子书版本网盘下载

离散数学引论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