离散数学复习大纲 (3).doc

2011－2012学年度离散数学考试复****大纲
第四部分 图论总结
第14章
一、图及其基本概念
图的定义（边集、结点集）
图的表示
图的阶、顶点数及边数
顶点相邻、边相邻及边与顶点的关联
结点的度
通路及回路
7、2011－2012学年度离散数学考试复****大纲
第四部分 图论总结
第14章
一、图及其基本概念
图的定义（边集、结点集）
图的表示
图的阶、顶点数及边数
顶点相邻、边相邻及边与顶点的关联
结点的度
通路及回路
7、图的连通性
二、图的基本性质
握手定理
握手定理的推论
第15章
三、几种特殊的图
1、欧拉图
定义、判定（充要条件）及寻找欧拉通路、欧拉回路。
2、哈密顿图
定义、判定（必要条件、充分条件）及寻找哈密顿通路、哈密顿回路（）。
3、二部图
定义、判定、互补结点子集、二部图是哈密顿图的条件（）
4、完全图
定义、判定及结点与边的关系
第16章
5、树
定义、性质、判定及结点与边的关系
6、生成树与最小生成树（）
根树
四、教材作业
1、P292页- P293页 8题、20题、29题、44题、45题
2、P306 2题、9题、13题
3、P318页- P319页 2题、7题、23题、25题、26题
第三部分 代数结构总结
第9章
一、运算
运算的定义
运算的封闭性
二元运算的特异元素
二元运算的性质
二、代数系统
1、代数系统的定义
2、子代数
第10章
三、群
1、半群、独异点
2、群的定义及判定（，及判断理由）
3、交换群
4、群的幂运算及元素的阶（理解定义后的例子，会求解）
4、子群与陪集
5、利用子群、陪集进行群分解
6、拉格朗日定理
7、群的性质
第11章
四、格
1、偏序集的定义
2、用哈斯图表示偏序集
3、偏序集中几特殊元素
4、格的定义、性质、判定及满足的算律
5、格的对偶原理
6、偏序集与格的关系
7、利用哈斯图判断一个偏序集是否为格
五、几种特殊的格
1、分配格及判断
2、有补格及判断
3、有补分配格判断
4、布尔格及判定（利用五角格与钻石格判断）
、、、
六、布尔代数的性质
七、教材作业
1、P178页-P179页 4题、7题、9题
2、P202页-P203页 4题、8题、9题
3、P218页 2题、4题、9题
第二部分 集合论总结
第6章
一、集合
1、集合及集合的表示方法：列举法与描述法
2、集合的集数
3、集合的子集及幂集
二、集合间的关系
1、集合间的包含关系
2、集合间的相等关系
3、集合间的真包含关系
三、集合的运算
1、集合的并、交
2、集合的绝对补与相对补运算
3、集合的对称差运算
四、有穷集合的计数
1、用文氏图解决有穷集的计数
2、用包含排斥原理解决穷集的计数
、
第7章
五、有序n元组与笛卡尔积
1、有序n元组与笛卡尔积
2、序偶
六、二元关系（简称为关系）
1、关系的定义