组合数学及其算法PDF电子书下载

第一章 引论 1

1.1 组合数学研究的对象 2

1.2 组合问题典型实例 4

1.2.1 分派问题 5

1.2.2 染色问题 5

1.2.3 幻方问题 6

1.2.4 36军官问题 8

1.2.5 中国邮路问题 9

习题 10

第二章 排列与组合 12

2.1 两个基本计数原理 12

2.2 无重集的排列与组合 14

2.3 重集的排列与组合 18

2.4.1 序数法 23

2.4 排列生成算法 23

2.4.2 字典序法 28

2.4.3 轮转法 30

2.5 组合生成算法 34

2.6 应用举例 35

习题 39

第三章 容斥原理 41

3.1 引言 41

3.2 容斥原理 42

3.3 几个重要公式 48

3.4 错位排列 51

3.5 有限制的排列 54

3.6 棋阵多项式 56

3.7 禁位排列 58

习题 61

第四章 鸽巢原理 64

4.1 鸽巢原理 64

4.2 鸽巢原理的推广形式 66

4.3 Ramsey数 69

4.4 Ramsey数的性质 72

4.5 Ramsey定理 74

习题 75

第五章 母函数 78

5.1 母函数概念 78

5.2 幂级数型母函数 79

5.3 整数的拆分 84

5.4 Ferrers图 90

5.5 指数型母函数 92

习题 98

第六章 递归关系 102

6.1 引言 102

6.2 几个典型的递归关系 103

6.3 用母函数方法求解递归关系 106

6.4 常系数线性齐次递归关系的求解 110

6.5 常系数线性非齐次递归关系的求解 120

6.6 非常系数非线性递归关系的求解 124

6.7 差分表法 127

6.8 Stirling数 136

习题 138

第七章 Polya定理 141

7.1 有限集的映射 141

7.2 群的基本概念 143

7.3 置换群 145

7.4 置换的奇偶性 149

7.5 置换群下的共轭类 152

7.6 Burnside引理 155

7.7 Polya定理 161

7.8 Polya定理的母函数型式 170

7.9 不标号图的计数 172

习题 176

第八章 图论基础 179

8.1 图的基本概念 179

8.2 同构图、完全图与二分图 185

8.3 通路、回路与图的连通性 188

8.4 Euler图与Hamilton图 192

8.5 割集与树 195

8.6 图的矩阵表示法 201

8.7 平面图、对偶图与色数 206

8.8 匹配理论 213

8.9 网络流 220

习题 225

第九章 拉丁方与区组设计 231

9.1 引言 231

9.2 拉丁方 232

9.3 有限域 236

9.4 正交拉丁方的构造 239

9.5 完全区组设计 242

9.6 平衡不完全区组设计（BIBD） 244

9.7 区组设计的构造 248

9.8 Steiner三连系 250

9.9 Hadamard矩阵 255

习题 260

第十章 线性规划 263

10.1 LP问题引例 264

10.2 LP问题的一般形式 265

10.3 LP问题的标准型 267

10.4 可行域和最优可行解 269

10.5 单纯形法 272

10.6 单纯形表格法 279

10.7 两阶段法 283

10.8 对偶原理 293

10.9 对偶单纯形法 302

10.10 应用举例 311

习题 319

第十一章 组合优化算法与计算的时间复杂度理论 323

11.1 Dijkstra算法 324

11.2 Floyd算法 329

11.3 Kruskal算法 333

11.4 求最优树的破圈法和统观法 335

11.5 二分图中最大匹配与最佳匹配的算法 339

11.6 Eleury算法 344

11.7 中国邮路问题及其算法 345

11.8 深度优先搜索法——DFS算法 352

11.9 项目网络与关键路径法 355

11.10 网络最大流算法 362

11.11 状态转移法 372

11.12 好算法、坏算法和NP类问题 375

11.13 NPC类问题 379

11.14 货郎问题的近似解 389

习题 391

参考文献 396