组合学与图论
基本信息作者：林翠琴
出版社：清华大学出版社
ISBN：9787302192220
定价：24.00元
装帧：平装
印刷日期：2009年3月18日
图书简介本书是在多次讲授“组合学与图论”课程的讲义基础上修改而成的.许多教科书将组合学和图论分开写成两本.考虑到大多数专业的教学学时的实际情况，本书将组合学和图论合写成一本，以方便教与学.本书对基本概念的叙述力求深入浅出，清晰准确；对定理的证明力求简明易懂而又严谨；对例题的选择力求典型、充实.本书的重点是使学生理解应用组合学和图论的知识去分析和处理问题的思想和方法，并通过丰富多样的例题使学生更好地掌握课程的基本内容，注重培养学生分析和解决实际问题的能力.为了便于学生自学，对书中配置的难易程度不同的三百多道习题，给出答案或提示或简明的解答（证明）过程.
本书可作为应用数学系、计算机系的本科生以及相关专业的研究生“组合学与图论”课程的教科书，也可作为“离散数学”课程的参考书.
图书目录第1章 组合学与图论中若干著名的古典问题1
1.1 Konigsberg七桥问题与中国邮递员问题1
1.2 Hamilton问题与旅行商问题2
1.3 幻方问题3
1.4 棋盘覆盖问题3
1.5 36军官问题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.1 Fibonacci数列的解法和性质30
3.2.2 生成函数法解常系数线性递推关系式34
3.2.3 特征根法解常系数线性递推关系式35
3.3 二重序列、Bernoulli多项式和Euler多项式42
3.3.1 二重序列42
3.3.2 Bernoulli多项式和Euler多项式43
习题45
目录目录第4章 包含与排斥原理48
4.1 包含与排斥原理48
4.2 包含与排斥原理的若干应用51
4.2.1 Eulerφ-函数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.2 Ramsey数69
5.2.1 Ramsey数的概念69
5.2.2 Ramsey数的性质70
5.2.3 Ramsey数的上下界70
习题71
第6章 Stirling数 划分与分拆73
6.1 正规多项式列和差分算子73
6.1.1 正规多项式列的概念73
6.1.2 几个常用的正规多项式列73
6.1.3 差分算子和移位算子74
6.2 Stirling数78
6.3 集的划分84
6.4 Bell数、Lah数87
6.4.1 Bell数87
6.4.2 Lah数89
6.5 自然数的分拆和Ferrers图90
6.5.1 自然数分拆的定义90
6.5.2 Ferrers图和分拆的共轭性91
6.5.3 分拆的性质92
习题99
第7章 反演公式与M?bius函数102
7.1 第一反演公式102
7.2 布置的格式数104
7.3 偏序关系与Mobius函数107
7.3.1 偏序关系107
7.3.2 Mobius函数110
7.3.3 Hasse图111
7.4 Mobius反演的一个应用--环状字的计数115
习题116
第8章 Polya计数理论119
8.1 置换群的循环指标与轨道119
8.2 Polya定理122
8.3 群的循环指标的计算125
8.4 赋权的Polya计数定理及其应用128
8.4.1 赋权的Polya计数定理128
8.4.2 Polya计数定理的应用129
8.4.3 Polya计数定理的一个推广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.1 Euler图159
11.2 偶图及其计数160
11.3 有向Euler图与高效率磁鼓设计161
11.4 无向图的Hamilton路与Hamilton圈162
11.5 韧度、连通度与独立数164
11.6 H-图的若干等价条件和充分条件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