《图论》课程标准

1、图论课程标准一、课程概述图论是数学与应用数学专业的一门专业课。它是研究离散对象二元关系系统的一个数学分支。它的特点是技巧强、实用性强。作为高校数学与应用数学专业的选修课之一,本课程的目的是介绍图论的一些重要结论；介绍图论证明的基本方法；介绍它的应用。通过本课程的学习，学生将会掌握图论的基本概念、基本理论和方法，了解一些基本的图论算法及其实现，且能将图论理论应用于一些简单的离散数学问题。二、课程目标1、 知道图论这门学科的性质，研究范围，研究方法，在数学中的地位、价值及与其它学科的联系。2、理解图论的理论、思想和方法，使学生会用其解决实际问题。3、通过图论的学习,培养学生的抽象思维和慎密概括的能

2、力。三、课程内容和教学要求对本学科各教学内容的要求分为：知道、理解、掌握、学会四个层次。其涵义分别解释如下：a) 知道是指对学习对象知其然，即知道它的内容。对于概念，指导其内涵和外延； 对于命题，指导其条件及结论；对于公式，知道其中每个符号所表述的意义和公式成立的条件；对于方法，知道它的详细步骤和适用于何种情况。b) 理解是指对学习对象不仅知其然且知其所以然。对于概念，不仅指导它的内涵和 外延，而且还知道它的现实原型，它的产生背景，它的各种常见的应用体现。对于定理，不仅指导它的条件和结论，而且还知道它的证明，它的各种常见变形。对于公式和方法，不仅达到知道这一层次的要求，而且能够自己推导并指导它

3、的各种变形。c) 掌握是指熟悉学习对象的内容，它和其他知识点的联系，能熟练地应用它来解决有关的问题。d) 学会是指能模仿或在教师指导下独立地完成某些教学知识任务，或能识别一般性的差错。以下以表格的形式列出本课程的教学内容，并在与之相应的层次栏中填“”。表示号的内容表示选学内容，教师可根据实际情况确定是否选作教学内容。 教 学 内 容教 学 要 求知道理解掌握学会1、 图（1） 图的概念（2） 子图（3） 顶点的度（4） 道路与连通性（5） 图的运算2、 树（1） 树的特性（2） 割边与割点（3） 生成树3、 欧拉图和哈密顿图（1） 环路（2） 欧拉图（3） 哈密顿图4、 割集（1） 割集与断集

4、（2） 关联集5、连通性 （1） 连通度和边连通度（2） 连通图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启发

5、、分析、引导、问题式教学欧拉图和哈密顿图4启发、分析、引导、问题式教学割集4启发、分析、引导、问题式教学连通性6启发、分析、引导、问题式教学匹配6启发、分析、引导、问题式教学色数6启发、分析、引导、问题式教学平面图4启发、分析、引导、问题式教学有向图6启发、分析、引导、问题式教学运输网络4启发、分析、引导、问题式教学（二）教学形式与教学方法建议（1） 教学班是主要的教学组织，建议教学形式或以分班进行课堂教学为主。（2） 教学中可根据具体情况，灵活选用各种教学方法和教学手段，如：讲授法、谈话法、自学辅导法、问题解决教学法、讲练几何法、直观教具辅助教学法、电化教学法、多媒体教学法等。总的原则是，应

6、当让“教”落实到学生的“学”，切忌“教”“学”脱节。应充分发挥教师的主导作用和督促作用，最大限度地调动起学生的学习积极性，使学生的主体地位得到充分的体现，使学生学得主动，学得生动活泼，轻松而不敢懈怠，紧张而不觉负荷过重。既注意学生知识的增长，更注意学生能力的增强。（3） 解题训练是学习数学的一个重要环节，因此每次课（两学时）后宜布置适量的作业，让学生通过作业消化和巩固所学的知识，并增强自己解决问题的能力。（4） 可根据具体情况，适当安排时间，以适当的方式对学生进行辅导。五、教材编写与选用1、 王朝瑞编著图论. 北京：北京理工大学出版社.2002.10.2、 陈子岐主编图论. 北京：高等教育出版

7、社.1990.5.六、课程评价本课程的评价以课程目标，教学内容和要求为依据。本课程的考核由平时考核和期末考试两个部分组成。平时考核包括学生上课出勤情况，作业情况，上课回答问题的情况，课堂联系情况，平时小考情况，课堂上或课外自学中提出新见解，新方法的情况等。期末考试采用闭卷笔试的方式进行，按百分制计分，60分及格，100分为满分，考试时间120分钟。考试题型可根据需要选用各种题型，如：选择题，填空题，判断题，求解题，证明题等。命题的覆盖率要比较广，各主要知识点要尽可能都考到。应按基本教学要求出题，无须受及格率或优秀率的约束。各类题型的比例宜按具体需要而定。平时考核成绩占总成绩的30%，期末考试成绩占总成绩的70%。样题与目标定位示例A选择题(15%)：（着重考查学生对知识的识别程度）例：设G为简单图，H为G的补图，下列说法正确的是( )。 (A)G与H都为连通图; (B) G与H都为非连通图;(C)若 G不连通，则H连通;(D)以上都不对。 B填空题(15%)：（着重考查学生对知识的理解程度）例：Kn有_条边；Km,n有_条边,有_个顶点. C判断题(15%)：（着重考查学生对知识的理解程度）例：若两个图的顶点数和边数都相同，则这两个图同构. （ ）。D求解题(20%)：（着重考查学生对知识的理解程