图论教学大纲

一、课程编号: 3103390

二、课程名称：图论

三、预修课程:线性代数、高等数学、数理逻辑

四、课程的性质、目的和任务：

本课程为必修课程。本课程与数理逻辑统称为离散数学。对于信息技术中的硬件和软件均表现为离散量的特征形式，而离散数学就是研究这些离散量的变化规律。离散数学是现代数学的重要分支，是计算机科学中基础理论的核心课程。它充分地描述了计算机科学离散性的特点，使其成为信息技术科学有力的工具。目前离散数学为计算机科学与技术专业的后继课如数字逻辑、逻辑程序设计、系统结构、操作系统、人工智能、数据结构、编译方法和算法分析等有着紧密的联系。它是一门综合性的专业基础课。

通过本课程的学习，应达到知识和能力两方面的目标：

   1．知识方面：学习二元关系和函数的基本概念。学习代数系统中的代数结构及其同态与同构的概念。初步掌握用抽象的方法了解对将要处理的数学对象集合上的关系或运算，为刻划抽象数据结构打下基础。学习图论的基本概念及其应用，为后继课程的学习打好基础。

   2．能力方面：使学生能得到严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维与计算机科学实践之间的内在联系，提高分析问题和解决问题的能力。

五、学分、学时安排

本课程讲授总时数为32学时，2学分。

六、本课程应掌握的基本概念、基本理论、基本技能

通过本课程的学习，学生应该掌握用二元关系表示离散函数的概念及其性质。在代数结构中，掌握抽象代数的运算和性质、两个代数系统间的同态和同构关系。并了解一种具体的代数结构--群。在图论中，在重点掌握图论的基本概念基础上，提高利用图论的方法进行论证和给出解决实际问题算法的能力。了解并掌握一种应用广泛的特殊图—树的应用，为后续课程“数据结构”的学习打下基础。通过本课程的学习，使学生能得到严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维与计算机科学实践之间的内在联系，不仅为专业后继课作准备，而且为信息技术教育打好数学基础

第八章  函数

• 课程主要内容

  知识点：函数的定义与性质

  函数的复合与反函数

• 教学目的与要求

  通过本章的学习应该达到下面的基本要求：

              1．能正确地理解关系与函数的区别。

  2．函数的运算特点：复合函数(即合成运算)、偏函数、置换。

  3．给定X到Y 上的函数f，能判别f的类型（映入函数、单射函数、映满函数、双射函数）,以及经运算后的类型,概念清楚、判定准确。

  4．能正确理解反函数的存在性及其判定。

  5．能理解将运算作为映射的概念，理解运算应满足的封闭性要求。

  本章重点：函数的概念及特殊函数的判别；反函数的定义及其性质、复合函数的性质。

       

        第十四章 图的基本概念

•     课程主要内容

  知识点：

                  1、图的基本定义及其表示、握手定理和相关性质、图的同构

                  2、通路与回路

                  3、图的连通性

                  4、图的矩阵表示、邻接矩阵及其可达矩阵

• 教学目的与要求

  通过本章的学习应该达到下面的基本要求：

           (1)图的有关基本概念：

图：无向图、有向图、子图、图的同构、简单图、完全图（有向与无向）、代权图、子图、图的同构的定义

结点与边：边的表示、邻接点与关联的边、结点的度（出度与入度）的定义、       结点的度与边数的关系、握手定理及其应用、可图化的特征等．

通路：简单通、初级通路、回路（初级与简单）、通路长度

(2)  图的连通性：无向连通图、有向图的弱连通、单向连通、强连通定义及其判别

结点的可达性：可达集合的确定

（3）图的邻接矩阵及其意义、邻接矩阵的运算及其性质：AA^T、、A^TA 、A²  、A³ …A^m中的元素值反映结点与路径的何种关系、可达矩阵及关联矩阵的定义、性质及其确定．

      第十六章 树

•     课程主要内容

  知识点：

                   1、无向树及其性质

                  2、生成树

                  3、根树及其应用

• 教学目的与要求

  通过本章的学习应该达到下面的基本要求：

    树的概念：树（有向与无向）、子树、森林、有序树、二叉树、完全二叉树、根结点、叶子结点、分支结点、结点的级。

最小生成树的求法

最优二叉树的求法

最佳前缀码的求法

        代数结构（包括第十章和第十一章的部分内容）

      第九章 代数系统

第十章 半群与群

•     课程主要内容

  知识点：

            二元运算及其性质

代数系统及其实例

群论的基本概念

• 教学目的与要求

  通过本章的学习应该达到下面的基本要求：

         (1)运算的定义、运算律(交换律，结合律、幂等律、分配律)的定义与判断

  （2）特殊元(零元、单位元及可逆元)的定义与确定．

  (3)代数系统、子代数及的定义，代数系统的同态(同构)的定义与性质．

          (4)群与半群的定义及基本性质．