课程号： 0013529
课程名称：集合论与图论
开课学期：春
学分： 3
先修课程：数学分析,线性代数，数据结构,
基本目的：学习和掌握集合论与图论的基本知识，重点培养学生处理二元关系类离散问题的综合能力。
内容提要：
第一部分：集合论 （共约18学时）
第一章：集合（2学时）
1） 集合的运算律，容斥原理 2）集合列的极限
第二章：基数（2学时）
1） 可数集与不可数集
2） 基数的比较，Cantor-Bernstein定理
3） 基数的运算
第三章：二元关系（约6学时）
1）二元关系的运算，性质与闭包
2）等价关系与集合的划分
3）偏序关系，链与反链，良序与超限归纳原理，选择公理与Zorn引理
第四章：布尔代数（约8学时）
1） 格的偏序特征与代数结构及其等价性 2）子格，格的同态与同构
3）模格，分配格，有补格 4）布尔代数，Stone表示定理5）布尔函数，析取范式与合取范式
第二部分：图论 （共约 27学时）
第一章：图的概念，运算与表示（3学时）
第二章：道路与回路（7学时）
1）道路与回路概述；2）最短道路，Dijkstra算法，Warshall-Floyd算法；
3）Euler图，DeBruijn序列；4）Hamilton图，k-方体与Gray码
第三章：树（约7学时）
1） 树的特征，回路系统与割集系统 2）基本树变换，最小生成树，Kruskal算法，Prim算法，破圈算法 3）根树，哈夫曼树与编码
第四章：平面图与图的着色（约4学时）
1） 平面图的性质与图的可平面性判定，对偶图
2） 点着色，边着色，平面图的域着色,四色定理
第五章：匹配，网络（约6学时）
1）图的连通性，连通度，Menger定理，可靠通讯网的构作
2）图的匹配与可增广道路，二部图的匹配，匈牙利算法
3）网络，可行流，增流路径，最大流与最小割切，Edmonds-Karp算法
教学方式：每周授课3学时
教材与参考书：
1.耿素云：集合论与图论，北京大学出版社，1998。
2.戴一奇，陈卫，胡冠章等：图论与代数结构，清华大学出版社，1995。
3.J.A.Bondy and U.S.R.Murty, Graph Theory with Applications,The Macmillan Press LTD ,1976。
4.Douglas B. West, Introduction to graph theory, 机械工业出版社（影印），2004。
学生成绩评定方法：作业20％，半期考30％，期考50％.
课程修订负责人：杨建生