组合学与图论

《组合学与图论》可作为应用数学系、计算机系的本科生以及相关专业的研究生“组合学与图论”课程的教科书，也可作为“离散数学”课程的参考书。

《组合学与图论》是在多次讲授“组合学与图论”课程的讲义基础上修改而成的，许多教科书将组合学和图论分开写成两本.考虑到大多数专业的教学学时的实际情况，《组合学与图论》将组合学和图论合写成一本，以方便教与学。《组合学与图论》对基本概念的叙述力求深入浅出，清晰准确；对定理的证明力求简明易懂而又严谨；对例题的选择力求典型、充实，《组合学与图论》的重点是使学生理解应用组合学和图论的知识去分析和处理问题的思想和方法，并通过丰富多样的例题使学生更好地掌握课程的基本内容，注重培养学生分析和解决实际问题的能力，为了便于学生自学，对书中配置的难易程度不同的三百多道习题，给出答案或提示或简明的解答（证明）过程。

第1章组合学与图论中若干著名的古典问题
1.1Knigsberg七桥问题与中国邮递员问题
1.2Hamilton问题与旅行商问题
1.3幻方问题
1.4棋盘覆盖问题
1.536军官问题
1.6鸽笼原理和Ramsey数
1.7四色问题
1.8平面图与网络

第2章排列组合布置
2.1映射的个数、排列与组合
2.2多项式系数与Gauss系数
2.3组合恒等式
习题

第3章生成函数和递推公式
3.1生成函数法
3.1.1生成函数的一般概念
3.1.2形式幂级数的运算
3.1.3生成函数的应用
3.2递推关系式
3.2.1Fibonacci数列的解法和性质
3.2.2生成函数法解常系数线性递推关系式
3.2.3特征根法解常系数线性递推关系式
3.3二重序列、Bernoulli多项式和Euler多项式
3.3.1二重序列
3.3.2Bernoulli多项式和Euler多项式
习题
目录目录

第4章包含与排斥原理
4.1包含与排斥原理
4.2包含与排斥原理的若干应用
4.2.1Eulerφ-函数
4.2.2错排问题
4.2.3夫妇对入座问题（Menage问题）
4.2.4满射函数的个数
4.2.5依赖于所有变量的Boolean函数的个数
4.2.6重数限定的可重组合数
4.2.7矩阵的恒久量和相异代表组
习题

第5章鸽笼原理和Ramsey数
5.1鸽笼原理
5.2Ramsey数
5.2.1Ramsey数的概念
5.2.2Ramsey数的性质
5.2.3Ramsey数的上下界
习题

第6章Stirling数划分与分拆
6.1正规多项式列和差分算子
6.1.1正规多项式列的概念
6.1.2几个常用的正规多项式列
6.1.3差分算子和移位算子
6.2Stirling数
6.3集的划分
6.4Bell数、Lah数
6.4.1Bell数
6.4.2Lah数
6.5自然数的分拆和Ferrers图
6.5.1自然数分拆的定义
6.5.2Ferrers图和分拆的共轭性
6.5.3分拆的性质
习题

第7章反演公式与Mbius函数
7.1第一反演公式
7.2布置的格式数
7.3偏序关系与Mbius函数
7.3.1偏序关系
7.3.2Mbius函数
7.3.3Hasse图
7.4Mbius反演的一个应用——环状字的计数
习题

第8章Pólya计数理论
8.1置换群的循环指标与轨道
8.2Pólya定理
8.3群的循环指标的计算
8.4赋权的Pólya计数定理及其应用
8.4.1赋权的Pólya计数定理
8.4.2Pólya计数定理的应用
8.4.3Pólya计数定理的一个推广
习题

第9章图与子图
9.1图的定义
9.2图的同构
9.3圈、完全图、二部图、补图
9.4顶点的度、正则图
9.5子图与图的运算
9.6路、回路与图的连通性
9.7邻接矩阵与关联矩阵，图的谱
习题

第10章树
10.1树的特征
10.2连通图的生成树与Cayley定理
10.3根树与树形图
10.4最小树
习题

第11章Euler图和Hamilton图
11.1Euler图
11.2偶图及其计数
11.3有向Euler图与高效率磁鼓设计
11.4无向图的Hamilton路与Hamilton圈
11.5韧度、连通度与独立数
11.6H-图的若干等价条件和充分条件
11.7中国邮路问题和旅行售货问题
习题

第12章图的匹配与因子分解
12.1图的匹配与覆盖
12.1.1图的匹配
12.1.2图的覆盖
12.2图的因子分解
习题

第13章图的平面性和着色
13.1图的平面性
13.2图的点、边和面着色
13.2.1图的色数和色临界图
13.2.2图的边着色（仅对无自环图而言）
13.2.3图的点着色
13.2.4平面图的点、边和面着色
13.3平面图的着色与四色定理
13.4图的色多项式
习题
习题答案与提示
主要参考资料