课程号：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％.
课程修订负责人：杨建生
