离散数学引论

本书以组合计数问题为重点，介绍了组合数学的基本原理和思想方法，全书共分8章：鸽巢原理，排列与组合，容斥原理，递推关系，生成函数，Polya计数理论，相异代表系，组合设计．取材的侧重点在于体现组合数学在计算机科学特别是在算法分析领域中的应用．每章后面都附有一定数量的习题，供读者练习和进一步思考． .

本书可作为计算机专业、应用数学专业研究生和高年级本科生的教材或教学参考书，也可供从事这方面工作的教学、科研和技术人员参考． ...

序 言

第一篇 图及其算法

1. 1 什么是图论

1. 2 图的定义

1. 3 Brouwer不动点定理

1. 4 Dijkstra算法

习题一

1. 5 树

1. 6 生成树

1. 6. 1 生成树的个数

1. 6. 2 最优生成树的Kruskal算法

1. 7 常用树

1. 7. 1 有序二元树

1. 7. 2 Huffman树

习题二

1. 8 平面图

1. 8. 1 平面图及其Euler公式

1. 8. 2 对偶图和极大平面图

1. 8. 3 Kuratowsky定理

1. 8. 4 图的厚度

习题三

1. 9 纵深搜索和平面嵌入算法

1. 9. 1 广度优先与深度优先搜索算法

1. 9. 2 求割顶和块的算法

1. 9. 3 有向图的DFS和极大强连通子图的算法

1. 9. 4 平面嵌入算法

习题四

1. 10 匹配

1. 10. 1 匹配理论

1. 10. 2 二分图中最大匹配与最佳匹配的算法

习题五

1. 11 图上遍历

1. 11. 1 Euler图

1. 11. 2 求Euler回路的算法

1. 11. 3 中国邮路问题

1. 11. 4 Harmihon图

习题六

1. 12 色

1. 12. 1 边色数

1. 12. 2 顶色数与面色数

1. 12. 3 色多项式

习题七

1. 13 支配集. 独立集和Ramsey数

1. 13. 1 支配集和独立集

1. 13. 2 a G ,

G , G 的计算

1. 13. 3 Ramsey数

1. 13. 4 多元Ramsey数和Schur定理

习题八

1. 14 有向图

1. 14. 1 有向图的连通性

1. 14. 2 有向轨与竞赛图

1. 14. 3 有向圈与竞赛图

1. 14. 4 有向Euler图

习题九

1. 15 网络流

1. 15. 1 Ford-Fulkerson最大流算法

1. 15. 2 Dinic最大流算法

1. 15. 3 有上下界的网络中的流

1. 15. 4 有供需约束的流

1. 15. 5 PERT问题

1. 15. 6 流与二分图

习题十

1. 16 连通度

1. 16. 1 无向图的顶连通度

1. 16. 2 有向图的顶连通度

1. 16. 3 无向图的边连通度

1. 16. 4 有向图的边连通度和弱独立外向生成树

1. 16. 5 可靠通讯网络

习题十一

第二篇 组合基础

2. 1 什么是组合论

2. 2 鸽笼原理

2. 3

×原理与排列组合

2. 3. 1 无重复的排列组合

2. 3. 2 Catalan数

2. 3. 3 可重复的排列组合

习题一

2. 4 容斥原理

习题二

2. 5 生成函数

2. 5. 1 生成函数概念

2. 5. 2 组合数的生成函数

2. 5. 3 拆分自然数

2. 5. 4 排列数的生成函数

习题三

2. 6 递归方程

2. 6. 1 递归方程的初值问题

2. 6. 2 线性常系数递归方程的生成函数解法

2. 6. 3 常系数线性齐次递归方程的特征值解法

2. 6. 4 常系数线性非齐次递归方程的解

2. 6. 5 递归方程的其它解法

2. 6. 6 Stirling数

习题四

第三篇 代数与计数

3. 1 代数系统及其性质

3. 1. 1 代数系统的定义

3. 1. 2 代数系统的同构与同态

3. 2 群. 环. 域

3. 2. 1 群

3. 2. 2 环

3. 2. 3 域

习题一

3. 3 置换群和循环群

3. 3. 1 置换

3. 3. 2 置换群与循环群

3. 4 Lagrange定理和Burnside定理

3. 5 Polya定理

习题二

3. 6 图的群

3. 6. 1 图的自同构群

3. 6. 2 有限群的Cayley图

习题三

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

4. 1 圈空间和断集空间

4. 1. 1 圈空间

4. 1. 2 断集空间

4. 2 关联矩阵和邻接矩阵

4. 2. 1 关联矩阵

4. 2. 2 邻接矩阵

4. 3 圈矩阵和割集矩阵

4. 4 开关网络分析

习题一

4. 5 拟阵

4. 5. 1 拟阵的概念

4. 5. 2 拟阵理论

习题二

4. 6 倒称矩阵与层次分析

4. 7 正交拉丁方

4. 8 区组设计与区组矩阵

4. 8. 1 BIBD问题

4. 8. 2 区组关联矩阵

4. 8. 3 Hadamard矩阵

4. 8. 4 区组设计的构作

4. 9 魔矩阵密码

习题三

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

5. 1 好算法和坏算法

5. 2 不确定Turing机和NP类问题

5. 3 NPC问题和Cook定理

5. 4 NPC中的组合问题

5. 5 NPC中的图论问题

习题

第六篇 数理逻辑

6. 1 命题逻辑

6. 1. 1命题及其真假

6. 1. 2 联结词与命题公式

6. 1. 3 真值表

6. 1. 4 等价公式. 代换定理与对偶定理

6. 1. 5 范式

6. 2 命题逻辑中的推理

6. 2. 1 蕴含关系

6. 2. 2 真值表推理法

6. 2. 3 直接推理法

6. 2. 4 间接推理法

习题一

6. 3 谓词逻辑

6. 3. 1 命题的谓词表达形式

6. 3. 2 量词

6. 3. 3 谓词公式及其变元

6. 3. 4 谓词逻辑中的等价定律. 代入规则

6. 4 谓词逻辑中的推理

习题二

参考文献