离散数学引论

序言
**篇图及其算法
1.1什么是图论
1.2图的定义
1.3Brouwer不动点定理
1.4Dijkstra算法
习题一
1.5树
1.6生成树
1.6.1生成树的个数
1.6.2*优生成树的Kruskal算法
1.7常用树
1.7.1有序二元树
1.7.2Huffman树
习题二
1.8平面图
1.8.1平面图及其Euler公式
1.8.2对偶图和极大平面图
1.8.3Kuratowsky定理
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.1Euler图
1.11.2求Euler回路的算法
1.11.3中国邮路问题
1.11.4Harmihon图
习题六
1.12色
1.12.1边色数
1.12.2顶色数与面色数
1.12.3色多项式
习题七
1.13支配集.独立集和Ramsey数
1.13.1支配集和独立集
1.13.2a（G）,B（G）,Y（G）的计算
1.13.3Ramsey数
1.13.4多元Ramsey数和Schur定理
习题八
1.14有向图
1.14.1有向图的连通性
1.14.2有向轨与竞赛图
1.14.3有向圈与竞赛图
1.14.4有向Euler图
习题九
1.15网络流
1.15.1Ford-Fulkerson*大流算法
1.15.2Dinic*大流算法
1.15.3有上下界的网络中的流
1.15.4有供需约束的流
1.15.5PERT问题
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.2Catalan数
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.6Stirling数
习题四
第三篇代数与计数
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.4Lagrange定理和Burnside定理
3.5Polya定理
习题二
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.1BIBD问题
4.8.2区组关联矩阵
4.8.3Hadamard矩阵
4.8.4区组设计的构作
4.9魔矩阵密码
习题三
第五篇不确定Turing机和计算的时间复杂度
5.1好算法和坏算法
5.2不确定Turing机和NP类问题
5.3NPC问题和Cook定理
5.4NPC中的组合问题
5.5NPC中的图论问题
习题
第六篇数理逻辑
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谓词逻辑中的推理
习题二
参考文献