离散数学

第1章 组合问题与技术引论

1.1 工程时间问题

1.1.1 问题

1.1.2 分析

1.1.3 关键路径分析

1.1.4 一个建筑的例子

练习1.1

1.2 匹配问题

1.2.1 问题

1.2.2 分析

1.2.3 排列

1.2.4 航空公司问题的解决方案的实用性

练习1.2

1.3 背包问题

1.3.1 问题

1.3.2 分析

1.3.3 问题的再次考察

练习1.3

1.4 算法及其效率

1.4.1 算法的比较

1.4.2 多项式求值

1.4.3 子集生成算法

1.4.4 冒泡排序

练习1.4

历史注记

补充练习

计算机题

推荐读物

第2章 集合、关系和函数

2.1 集合运算

练习2.1

2.2 等价关系

练习2.2

2.3 同余关系

练习2.3

2.4 部分序关系

2.4.1 哈斯图

2.4.2 拓扑排序

练习2.4

2.5 函数

练习2.5

2.6 数学归纳法

练习2.6

2.7 应用

练习2.7

历史注记

补充练习

计算机题

推荐读物

第3章 图

3.1 图及其表示

3.1.1 图的其他表示

3.1.2 同构

练习3.1

3.2 通路和回路

3.2.1 欧拉回路和欧拉通路

3.2.2 哈密顿回路和通路

练习3.2

3.3 最短通路和距离

3.3.1 带权图

3.3.2 通路的数目

练习3.3

3.4 图着色

练习3.4

3.5 有向图和有向多重图

3.5.1 有向图的表示

3.5.2 有向多重图

3.5.3 有向欧拉回路和通路

3.5.4 有向哈密顿回路和通路

练习3.5

历史注记

补充练习

计算机题

推荐读物

第4章 树

……

第5章 匹配

第6章 网络流

第7章 计数技术

第8章 递推关系与生成函数

第9章 组合电路和有限状态机

附录A 逻辑和证明简介

附录B 矩阵

附录C 本书中的算法

附录D 各章奇数练习题答案

参考书目

历史注记的参考书目

本书是离散数学的入门教材，充分考虑到了初学者的需要，内容、例题、习题都作了精心的挑选和组织，讲解细致，叙述浅显易懂，循序渐进，用例贴近日常生活或计算机应用，并注重算法。主要内容包括集合、关系、函数、图论、组合数学、组合电路设计、有限自动机、算法、逻辑等。 　　本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书。