《图论》课程标准
一、课程概述
图论是数学与应用数学专业的一门专业课。它是研究离散对象二元关系系统的一个数学分支。它的特点是技巧强、实用性强。作为高校数学与应用数学专业的选修课之一,本课程的目的是介绍图论的一些重要结论；介绍图论证明的基本方法；介绍它的应用。
通过本课程的学习，学生将会掌握图论的基本概念、基本理论和方法，了解一些基本的图论算法及其实现，且能将图论理论应用于一些简单的离散数学问题。
二、课程目标
1、 知道《图论》这门学科的性质，研究范围，研究方法，在数学中的地位、价值及与
其它学科的联系。
2、理解图论的理论、思想和方法，使学生会用其解决实际问题。 3、通过图论的学习,培养学生的抽象思维和慎密概括的能力。
三、课程内容和教学要求
对本学科各教学内容的要求分为：知道、理解、掌握、学会四个层次。其涵义分别解释如下：
a) 知道—是指对学习对象知其然，即知道它的内容。对于概念，指导其内涵和外延；
对于命题，指导其条件及结论；对于公式，知道其中每个符号所表述的意义和公式成立的条件；对于方法，知道它的详细步骤和适用于何种情况。
b) 理解—是指对学习对象不仅知其然且知其所以然。对于概念，不仅指导它的内涵和
外延，而且还知道它的现实原型，它的产生背景，它的各种常见的应用体现。对于定理，不仅指导它的条件和结论，而且还知道它的证明，它的各种常见变形。对于公式和方法，不仅达到知道这一层次的要求，而且能够自己推导并指导它的各种变形。
c) 掌握—是指熟悉学习对象的内容，它和其他知识点的联系，能熟练地应用它来解决
有关的问题。
d) 学会—是指能模仿或在教师指导下独立地完成某些教学知识任务，或能识别一般性的差错。
以下以表格的形式列出本课程的教学内容，并在与之相应的层次栏中填“?”。表
《图论》课程标准第 1 页 共 5 页
示＊号的内容表示选学内容，教师可根据实际情况确定是否选作教学内容。
教 学 内 容 知 道 1、 图 （1） 图的概念 （2） 子图 （3） 顶点的度 （4） 道路与连通性 （5） 图的运算 2、 树 （1） 树的特性 （2） 割边与割点 （3） 生成树 3、 欧拉图和哈密顿图 （1） 环路 （2） 欧拉图 （3） 哈密顿图 4、 割集 （1） 割集与断集 （2） 关联集 5、连通性 （1） 连通度和边连通度 （2） 连通图 教 学 要 求 理 解 掌 握 学会 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 《图论》课程标准第 2 页 共 5 页
6、匹配 （1） 最大匹配 （2） 二部图的匹配与覆盖 （3） 完美匹配 （4） 完美匹配的算法 7、色数 （1） 独立集 （2） 顶点着色 （3） 边着色 （4） 色多项式 8、平面图 （1） 平面图的概念 （2） 欧拉公式 （3） 对偶图 9、有向图 （1） 有向图 （2） 有向道路和有向圈 （3） 有向树和有序树 10、运输网络 （1） 网络的流 （2） 割 （3） 最大流最小割定理 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 四、课程实施
（一）课时安排与教学建议
本课程教学内容安排在第三个学期完成，总共54学时，每周安排3学时，具体安排如下：
主要内容 图 树
课时建议 6 6 教与学的建议 启发、分析、引导、问题式教学 启发、分析、引导、问题式教学 《图论》课程标准第 3 页 共 5 页