2013离散数学复习大纲.doc

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