集合论与图论课程详细信息
课程号 英文名称 先修课程 中文简介 英文简介 开课院系 通选课领域 是否属于艺术与美育 平台课性质 平台课类型 授课语言 00135290 Set Theory and Graph Theory 高等数学,线性代数，数据结构 学习和掌握集合论与图论的基本知识，重点培养学生处理二元关系类离散问题的综合能力。 An introductory course to set thory and graph theory. 数学科学学院 否 中文 Discrete Mathematics and Its Application,7） K.H.Rosen,McGraw-Hill 教材 & 机械工,图论,3） 王朝瑞,北京理工大学出版社,图论与代数结构,2） 戴一奇，陈卫，胡冠章等,清华大学出版社,集合论与图论,耿素云,北京大学出版社； 参考书 学习和掌握集合论与图论的基本知识，重点培养学生处理二元关系类离散问题的综合能力。 第一部分：集合论 （共约18学时） 一、集合（2学时） 1） 集合的运算律，容斥原理 2） 集合列的极限 二、基数（2学时） 1） 可数集与不可数集 2） 基数的比较，Cantor-Bernstein定理 3） 基数的性质，连续统假设，Cantor定理 教学大纲 三、二元关系（约6学时） 1）二元关系的运算，性质与闭包 2）等价关系与集合的划分 3）偏序关系，链与反链，良序与超限归纳原理 四、布尔代数（约8学时） 1） 格的偏序特征与代数结构及其等价性 2）子格，格的同态与同构 3）模格，分配格，有补格 4） 布尔代数，Stone表示定理 5） 布尔函数，析取范式与合取范式 第二部分：图论 （共约 27学时） 一、图的概念，运算与表示（3学时） 学分 3
二、道路与回路（9学时） 1）道路与回路概述， 2）图的连通性，连通度，Menger定理，可靠通讯网的构作 3）最短道路，Dijkstra算法，Warshall-Floyd算法 4）Euler图，DeBruijn序列 5）Hamilton图，k-方体与Gray码 三、树（约7学时） 1） 树的特征，回路系统与割集系统 2）基本树变换，最小生成树，Kruskal算法，Prim算法 2） 根树，哈夫曼树与编码 四、平面图与图的着色（约4学时） 1） 平面图的性质与图的可平面性判定，对偶图 2） 点着色，边着色，平面图的域着色,四色定理 五、匹配，网络（约4学时） 1）图的匹配与可增广道路，二部图的匹配，匈牙利算法 2）网络，可行流，最大流与最小割切，Edmonds-Karp算法 教材与参考书： 1） 耿素云：集合论与图论，北京大学出版社。 2） 戴一奇，陈卫，胡冠章等：图论与代数结构，清华大学出版社。 3） 王朝瑞：图论，北京理工大学出版社。 4） 王树禾：图论及其算法，中国科学技术大学出版社。 5） J.A.Bondy and U.S.R.Murty:Graph Theory with Applications,The Macmillan Press LTD. 6） E.G.Goodaire,M.M.Parmenter:Discrete Mathematics with Graph theory. 7） K.H.Rosen:Discrete Mathematics and Its Applications,McGraw-Hill & 机械工 业出版社。 教学方式：每周授课3学时 学生成绩评定方法：作业20％，期中考试30％，期末考试50％. 教学评估 杨建生：
集合论与图论课程
