集合与图论教学目的与要求：教学方式：考核方式：

372.068.1集合与图论(Settheory&Graphtheory)学分数3周学时3+1教学目的与要求：课程性质：计算机科学与技术专业本科生的核心课程。本课程前行课程为线性代数，微积分(上)。教学目的：有关集合与图论的内容在算法、语言、数据库、网络理论、操作系统和人工智能等方面起着很大的作用。通过本课程学习，帮助学生掌握集合论、组合学和图论的基础概念和解决问题的方法，为进一步学习后续课程，如代数结构与数理逻辑、数据结构、算法设计与分析、数据库引论等课程打下必要基础。基本内容：本课程基本内容由集合论初步，组合学初步和图论三部分组成，着重介绍基本概念、基本原理及典型应用。基本要求：学生应按本教学大纲要求，掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。为进一步学习计算机其他课程打下坚实的基础。教学方式：本课程以课堂讲授为主，课程共计54+18学时。考核方式：平时作业和期中，期末的两次笔试考试。教学用书：教材：《离散数学教程》朱洪、胡美琛、张蔼珠、赵一鸣编著上海科学技术文献出版社2002年8月参考书：Discretemathematicalstructures(Thirdedition),BernardKolman,RobertC.BusbySharonRoss1996，PrenticeHallInc.IntroductoryCombinatorics,R.A.Brualdi,1977,ElsevierNorthHollandInc.Algorithmicgraphtheory,AlanGibbons,1985集合论与图论北京大学出版社，1998年代数结构与组合数学屈婉玲北京大学出版社，1998年教学内容及学时分配第一章集合的基本概念（3学时）掌握：集合的基本概念，集合的运算。了解：集合论的悖论。讲课要点：1.1集合的表示1.2集合的子集1.3笛卡尔积1.4集合的运算1.5罗素悖论第二章关系（7学时）掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。了解：关系在关系数据库中的应用。讲课要点：2.1二元关系2.2关系的性质2.3关系的运算2.4关系数据库的一个实例2.5关系的闭包2.6等价关系与划分2.7次序关系第三章函数（2学时）掌握：函数的基本概念，复合函数和逆函数。了解：集合的特征函数。讲课要点：3.1函数的基本概念3.2逆函数与复合函数3.3集合的特征函数第四章无限集（8学时）掌握：基数及基数的比较，判断可列集与不可列集的方法。了解：集合的递归定义。讲课要点：4.1函数的递归定义与自然数集合4.2基数4.3可列集与不可列集4.4基数的比较第五章鸽笼原理（2学时）掌握：利用鸽笼原理解决组合数学中一些存在性问题的技巧。讲课要点：5.1鸽笼原理的简单形式5.2鸽笼原理的加强形式第六章排列与组合（7学时）掌握：集合的排列与组合，多重集的排列与组合等计数方法，有序划分和无序划分。讲课要点：6.1基本计数原理6.2集合的排列6.3集合的组合6.4多重集的排列和组合6.5有序划分和无序划分6.6容斥原理第七章生成函数与递推关系（7学时）掌握：用生成函数和递推关系解决组合计数问题的方法，以及求解递推关系的生成函数方法。了解：求解递推关系的特征根方法。讲课要点：7.l幂级数型生成函数7.2指数型生成函数7.3递推关系第八章图的基本概念（12学时）掌握：图的基本术语，路、回路和连通的基本概念，求最短路的算法及算法正确性证明，欧拉图和哈密顿图的基本概念、判别方法以及有关定理。讲课要点：8.1图的基本术语8.2路与回路8.3欧拉图8.4哈密顿图8.5最短路第九章平面图和图的着色（7学时）要求掌握平面图的基本概念、平面图的特征和欧拉公式，掌握图的点着色和平面图的面着色概念。了解图的边着色概念。讲课要点：9.1平面图与欧拉公式9.2顶点着色9.3平面图的着色9.4边的着色第十章树（7学时）掌握：树的基本性质和生成树、割集、有根树的概念，求最小生成树和最优树的算法及算法的正确性证明。了解：树的计数问题。讲课要点：10.1树及其性质10.2生成树与割集10.3最小生成树10.4树的计数10.5有根树与二分树10.6最优树第十一章连通度、网络与匹配（10学时）掌握：点连通度和边连通度的基本概念，掌握最大网络流算法及算法正确性证明，掌握匹配的基本概念和判别方法，掌握独立集和覆盖的基本概念和有关定理及证明方法。了解：佩特里网及其图的表示。讲课要点：11.l连通度与块11.2网络最大流11.3图与二分图的匹配11.4独立集,覆盖11.5佩特里网