要想用计算机解决问题就要为它建立数学模型,即描述研究对象及对象与对象之间的联系,并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。
本课程的目标是通过理论学习,使学生正确地理解概念,正确地使用概念进行推理,养成一个好的思维习惯,理解理论与实践的关系。引导学生观察生活、社会和大自然,分析事物间的联系,建立系统的模型,提出和解决其中的复杂工程问题。
本课程主要包含二部分内容:集合论与图论。集合论是整个数学的基础,也是计算机科学的基础,计算机科学领域中的大多数基本概念和理论,几乎均采用集合论的有关术语来描述和论证,而图论的基本知识则将始终陪伴着每一个计算机工作者的职业生涯。
计算学科以抽象、理论、设计为其学科形态,以数学方法和系统方法为其学科方法,本课程的核心目标就是在抽象和理论的基础上提供数学方法,因此,本课程是整个专业的基础课程,是计算机专业最重要的课程之一。
《集合论与图论》(上)主要讲述集合论部分,《集合论与图论》(下)主要讲述图论部分。
课程具体目标如下:
课程目标1:掌握集合论与图论的基本概念、基本原理、基本方法等基本知识,培养形式化、模型化的抽象思维能力,使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题,逐步学会为计算类复杂工程问题建立数学模型;
课程目标2:掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法,培养机械化、自动化的逻辑推理能力,使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题,并能获得有效的结论,理解并逐步设计求解这些问题的算法基本思想;
课程目标3:掌握资料查阅方法,学会对课堂所学理论知识进行扩展,培养自学能力。
课程目标4:能够利用本课所学知识分析工程实际问题或针对某些应用背景探讨所学知识的局限性,培养学生的独立思考与创新能力。
第1讲 图的基本概念
1.1 课前准备-图论
1.2 简史
1.3 图
1.4 图的表示
1.5 图模型
1.6 子图
1.7 度
1.8 正则图
1.9 同构
课件
第1讲测验
第2讲 连通图、补图、偶图
2.1 路、圈
2.2 连通图
2.3 判定是否连通
2.4 几类证明方法
2.5 判定是否有圈
2.6 关于路和圈的一个定理
2.7 补图
2.8 双图
2.9 图兰定理
2.10 极图理论
第2讲测验
第3讲 欧拉图
3.1 欧拉图、欧拉定理
3.2 欧拉定理的扩展
第3讲测验
第4讲 哈密顿图
4.1 背景
4.2 哈密顿图
4.3 哈密顿图判定的必要条件
4.4 哈密顿图判定的充分条件
第4讲测验
第5讲 图的表示、带权图
5.1 邻接矩阵
5.2 邻接表
5.3 关联矩阵
5.4 图解
5.5 带权图
第5讲测验
第6讲 树、割集
6.1 树的定义
6.2 树的性质
6.3 极小连通图
6.4 树的中心
6.5 生成树
6.6 最小生成树
6.7 割点
6.8 割点的性质
第6讲测验
第7讲 图的连通度
7.1 背景
7.2 顶点连通度和边连通度
7.3 顶点连通度和边连通度的关系
7.4 n连通
7.5 明格尔定理
7.6 柯尼希定理
7.7 网络流问题
第7讲测验
第8讲 匹配问题
8.1 独立集
8.2 偶图的匹配
8.3 偶图匹配的条件
8.4 相异代表系
第8讲测验
第9讲 平面图
9.1 背景
9.2 平面图的定义
9.3 欧拉公式
9.4 例题
9.5 非哈密顿平面图
9.6 库拉托夫斯基定理
第9讲测验
第10讲 图的顶点着色问题
10.1 图的顶点着色
10.2 色数的上、下界
10.3 四色定理 vs 五色定理
第10讲测验
第11讲 有向图的基本概念
11.5 有向路、有向圈
11.6 邻接矩阵
11.1 有向图的表示
11.2 有向图中顶点的度
11.3 有向完全图
11.4 有向图的同构
第11讲测验
第12讲 有根树、有序树、比赛图
12.1 有根树、有序树
12.2 比赛图
第12讲测验
工科数学分析、线性代数
1.《离散数学引论》(修订版),王义和编著,哈尔滨工业大学出版,2016
2.《离散数学教程》,耿素云等编著,北京大学出版社,2015
3.《离散数学》,左孝凌等编著,上海科技文献出版社,2016