课程号: 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.耿素云:集合论与图论,williamhill体育在线平台出版社,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%.
课程修订负责人:杨建生