《集合论与图论》教学大纲

课程编号：N1030010

课程中文名称：集合论与图论

课程英文名称：SET THEORY AND GRAPH THEORY

总学时：48  讲课学时：48 实验：0  总学分：3

授课对象：计算机科学与技术、信息安全、生物信息技术、软件工程专业

先修课程：高等数学、线性代数

课程要求：必修课

课程分类：专业基础课

开课单位：计算机科学与技术学院

课程教学目的

本课程的内容为后继的专业基础课及专业课提供必要的数学工具，描述数学模型，从而为描述数学模型（离散）提供了数学语言。更重要的是对培养学生的抽象思维和严格的逻辑推理能力有极大作用，对提高学生的分析问题和解决问题的能力，提高学生的数学修养及计算机科学的素质有很大的帮助。

一、 教学内容及学时安排

本课程的内容分为两部分，即集合论、图论。集合论是整个数学基础之一。图论虽是一个独立的分支，在本课中可视为集合论的一个应用，它研究在一个有限集合上定义了一个二元关系所组成的系统。研究任意离散系统，要为它建立数学模型，就要描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事务的运动规律。集合论与图论为此提供了强有力的描述工具与推力理论，而具有一个二元关系的有限系统用图作为模型是十分自然而有用。教学内容包括：

1．集合及其运算（6学时）

集合、子集、集合的相等关系、幂集；集合并、交、差、对称差、余集、迪卡尔乘积运算，各运算的性质及相互联系；有穷集合的基数、基本计数法则、容斥原理及应用。

2．映射（8学时）

基本定义、抽屉原理、映射的一般性质、映射的合成、逆映射、置换、二元运算、应用。

3．关系（10学时）

二（n）元关系、几个特殊二元关系、二元关系的表示、关系的合成运算、传递闭包、等价关系与集合的划分、偏序关系。

4．无穷集合的基数（6学时）

可数集及其性质、存在不可数集—对角线法，基数及其比较、连续统、罗素悖论与数学危机。

5．模糊集合论（0学时）

由于学时限制，本章只介绍这一新兴分支是怎样由经典集合推广到模糊集合、

介绍它的应用范围。因此，只让学生了解这一分支，在应用中有能力自学或看懂有关文献。

6．图的基本概念（8学时）

图、路、圈、连通图、偶图、补图、欧拉图、哈密顿图、图的邻接矩阵、最短路径问题。

7．树和割集（4学时）

树及其性质、生成树、割点和桥及其特征性质，最小生成树问题。

8．连通度和匹配（2学时）

顶点连通度与边连通度及其关系、偶图的匹配、Hall定理。

9．平面图和图的着色（4学时）

平面图及其欧拉公式、图的着色、五色定理，介绍计算机证明四色猜想。

10．有向图（6学时）

有向路、有向圈、强连通、强分支、有向图的矩阵表示、有根树、有序树、二元树、比赛图。

11．总结

三、教学基本要求

1．课程基本要求

课程的基本要求是掌握集合论、图论的基本概念、原理等基本知识，学会运用基本知识进行推理并应用到计算机科学领域解决实际问题。

2．考试基本要求

本课程笔试，考卷中考核概念是否理解占35%，是否掌握基本理论和基本方法占35%，考核学生能否灵活应用基本概念、基本理论、基本方法占15%，较难题占5%，作业占10%。

总计满分为100分。