图论-重庆师范大学-数学学院.doc

课 程 教 学 大 纲 (理论课) 课 程 名 称： 图论 适 用 专 业： 数学与应用数学 课 程 类 别： 学科基础课程 制 订 时 间： 2006年9月 数学与计算机科学学院 制 《图 论》课程教学大纲 （2005年制定，2007年修订） 一、课程代码：0501122003 二、课程类别：学科基础课程（选修） 三、预修课程：高等代数 四、学 分：3学分 五、学 时：54学时 六、课程概述： 《图论》是近二十年来发展十分迅速，应用比较广泛的一个新兴的数学分支，在许多领域，诸如物理学、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理各方面都有广泛的应用。因此受到世界数学界和工程技术界越来越广泛的重视。这门课程是来源于实际的一门学科，与实际结合非常紧密。自从它产生以后便蓬勃的发展起来，并与其它很多学科建立了联系。用图论的相关知识和方法可以解决许多其它学科中的问题以及一些实际生活中的问题。 《图论》这门课程主要包括无向图和有向图两大部分。其中在无向图中，主要研究图与子图、Euler图和Hamilton图、通路的集合和最短道路、树、割集、图的连通度、图的矩阵表示以及平面图等多个内容。在有向图中，主要介绍有向图的基本概念、有向图的矩阵表示、生成树的生成、网络流等内容。 七、教学目的： 《图论》这门课程的学习，主要掌握图论的基本内容和基本方法。通过对无向图部分的学习，首先要让学生理解图论中图的实质，要把它与几何中的几何图形区别开，即掌握图的定义以及与图有关的其它相关概念；同时要掌握一些特殊图类如：E图、H图、树、平面图等的基本概念和判别它们的条件，以及与它们相关的一些概念，并了解它们在实际中的应用；而且还要掌握割集、图的连通度、图的矩阵表示等具体含义。通过对有向图相关内容的学习，要掌握有向图的基本概念及关于它的一些重要应用。 总之，通过这门课程的学习，培养学生的抽象思维能力及应用图论知识解决问题的能力，从而提高学生的的综合素质。 八、学时分配表 教学内容(章) 理论学时 实验学时 习题课 其它 备注 第一章 图 3 1 第二章 树 4 2 第三章 欧拉图和哈密顿图 4 1 第四章 割集 3 1 第五章 圈空间与割集空间 4 1 第六章 图的矩阵表示 3 1 第七章 连通性 8 2 第八章 匹配 3 1 第九章 色数 3 1 第十章 平面图 6 2 第十一章 最短路与最小树 3 1 第十二章 有向图 4 2 第十三章 有向图的矩阵表示 2 第十四章 运输网络 3 1 九、教学基本内容： 图 7学时 教学要求： 本章的目的要求是：理解图的基本概念以及子图、顶点的度等定义；掌握握手引理；理解几类特殊图如：导出图、二部图等的定义；掌握二部图的判别条件；掌握道路与连通性的概念及相关结论；了解图的运算。 本章的重点是图的定义及相关概念；一些特殊图的定义及性质。难点是图的定义。 教学内容： 一、图的概念 引例 二元关系 图的定义 二、子图 三、顶点的度 顶点的度的定义 握手引理 四、道路与连通性 道路的定义 连通性的定义 二部图的判别条件 五、图的运算 图的并运算 图的交运算 图的差运算 图的对称差运算 树 3学时 教学要求： 本章的目的要求是：理解树的定义及一个图是树的充要条件；掌握割点和割边的定义及性质；知道生成树的概念及生成树的求法。 本章的重点是树的定义及性质；生成树的定义及求法。难点是树的充分必要条件。 教学内容： 树的特性 树的定义 树的性质 树的判别条件 割边与割点 割边的定义 割边的性质 割点的定义 割点的性质 生成树 生成树的定义 生成树的求法 欧拉图和哈密尔顿图 4学时 教学要求： 本章的目的要求是：了解环路的定义及性质；理解欧拉图的定义；掌握欧拉图的充要条件；理解哈密尔顿图的定义；掌握哈密尔顿图的必要条件和充分条件；了解图的闭包运算。 本章的重点是欧拉图的定义；判别欧拉图的充要条件；哈密尔顿图的定义；判别哈密尔顿图的必要条件和充分条件。难点是判别欧拉图的充要条件与判别哈密尔顿图的必要条件和充分条件。 教学内容： 环路 环路的定义 环路的性质 欧拉图 欧拉图的定义 欧拉图的充要条件 哈密尔顿图 哈密尔顿图的定义 哈密尔顿图的必要条件 哈密尔顿图的充分条件 图的闭包运算 割集 2学时 教学要求： 本章的目的要求是：理解割集与断集的定义；掌握割集与断集的性质；了解关联集的定义及性质。 本章的重点是割集与断集的定义；割集与断集的性质。这也是本章的难点。 教学内容： 割集与断集 割集的定义 断集的