组合学与图论PDF电子书下载

第1章 组合学与图论中若干著名的古典问题 1

1.1K？nigsberg七桥问题与中国邮递员问题 1

1.2Hamilton问题与旅行商问题 2

1.3幻方问题 3

1.4棋盘覆盖问题 3

1.536军官问题 4

1.6鸽笼原理和Ramsey数 4

1.7四色问题 5

1.8平面图与网络 5

第2章 排列 组合 布置 6

2.1映射的个数、排列与组合 6

2.2多项式系数与Gauss系数 15

2.3组合恒等式 18

习题 23

第3章 生成函数和递推公式 25

3.1生成函数法 25

3.1.1生成函数的一般概念 25

3.1.2形式幂级数的运算 27

3.1.3生成函数的应用 29

3.2递推关系式 30

3.2.1Fibonacci数列的解法和性质 30

3.2.2生成函数法解常系数线性递推关系式 34

3.2.3特征根法解常系数线性递推关系式 35

3.3二重序列、Bernoulli多项式和Euler多项式 42

3.3.1二重序列 42

3.3.2Bernoulli多项式和Euler多项式 43

习题 45

第4章 包含与排斥原理 48

4.1包含与排斥原理 48

4.2包含与排斥原理的若干应用 51

4.2.1Eulerψ-函数 51

4.2.2错排问题 53

4.2.3夫妇对入座问题（Menage问题） 55

4.2.4满射函数的个数 58

4.2.5依赖于所有变量的Boolean函数的个数 58

4.2.6重数限定的可重组合数 59

4.2.7矩阵的恒久量和相异代表组 61

习题 64

第5章 鸽笼原理和Ramsey数 66

5.1鸽笼原理 66

5.2Ramsey数 69

5.2.1Ramsey数的概念 69

5.2.2Ramsey数的性质 70

5.2.3Ramsey数的上下界 70

习题 71

第6章 Stirling数 划分与分拆 73

6.1正规多项式列和差分算子 73

6.1.1正规多项式列的概念 73

6.1.2几个常用的正规多项式列 73

6.1.3差分算子和移位算子 74

6.2Stirling数 78

6.3集的划分 84

6.4Bell数、Lah数 87

6.4.1Bell数 87

6.4.2Lah数 89

6.5自然数的分拆和Ferrers图 90

6.5.1自然数分拆的定义 90

6.5.2Ferrers图和分拆的共轭性 91

6.5.3分拆的性质 92

习题 99

第7章 反演公式与M？bius函数 102

7.1第一反演公式 102

7.2布置的格式数 104

7.3偏序关系与M？bius函数 107

7.3.1偏序关系 107

7.3.2M？bius函数 110

7.3.3Hasse图 111

7.4M？bius反演的一个应用——环状字的计数 115

习题 116

第8章 Pólya计数理论 119

8.1置换群的循环指标与轨道 119

8.2Pólya定理 122

8.3群的循环指标的计算 125

8.4赋权的Pólya计数定理及其应用 128

8.4.1赋权的Pólya计数定理 128

8.4.2Pólya计数定理的应用 129

8.4.3Pólya计数定理的一个推广 131

习题 133

第9章 图与子图 136

9.1图的定义 136

9.2图的同构 137

9.3圈、完全图、二部图、补图 137

9.4顶点的度、正则图 138

9.5子图与图的运算 139

9.6路、回路与图的连通性 140

9.7邻接矩阵与关联矩阵，图的谱 141

习题 142

第10章 树 145

10.1树的特征 145

10.2连通图的生成树与Cayley定理 147

10.3根树与树形图 152

10.4最小树 156

习题 156

第11章 Euler图和Hamilton图 159

11.1Euler图 159

11.2偶图及其计数 160

11.3有向Euler图与高效率磁鼓设计 161

11.4无向图的Hamilton路与Hamilton圈 162

11.5韧度、连通度与独立数 164

11.6H-图的若干等价条件和充分条件 166

11.7中国邮路问题和旅行售货问题 169

习题 170

第12章 图的匹配与因子分解 173

12.1图的匹配与覆盖 173

12.1.1图的匹配 173

12.1.2图的覆盖 174

12.2图的因子分解 175

习题 178

第13章 图的平面性和着色 180

13.1图的平面性 180

13.2图的点、边和面着色 183

13.2.1图的色数和色临界图 183

13.2.2图的边着色（仅对无自环图而言） 184

13.2.3图的点着色 184

13.2.4平面图的点、边和面着色 186

13.3平面图的着色与四色定理 187

13.4图的色多项式 188

习题 190

习题答案与提示 193

主要参考资料 209