《组合数学及其算法》求取 ⇩

第一章引论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