《图论》课程教学大纲

1、图论课程教学大纲 一、课程信息课程名称（COURSE TITLE）图论课程性质（COURSE CHARACTER）专业选修课（考查）课程代码（COURSE CODE）316B1009学分（CREDIT）2学时（CONTACT HOURS）32先修课程（PRE-COURSE）中学数学 计算机及程序设计课程负责人（COURSE COORDINATOR）适用专业数学与应用数学（师范）课程简介：图论是数学中一个既古老又年轻的分支。欧拉1736年关于哥尼斯堡七桥问题的论文标志着图论的诞生。近几十年来，由于运筹学、计算科学等学科的促进，图论正经历着一个蓬勃发展的时期，它在计算机科学、运筹学、电网络分析、化

2、学、物理学以及社会科学等方面已取得丰富的成果。 图论具有直观、清晰、易懂的特点，技巧性较强，有广泛的应用。通过本课程的学习，要求学生了解或掌握路和圈、树、平面图、匹配、图染色等方面的基本概念、基本理论和基本方法。加强学生的感性与理性认识，培养学生理论联系实际，分析和解决问题的能力。二、课程目标通过本课程的学习，学生应具备以下几方面的目标：1.通过本课程学习，学生掌握图论的基本概念、基本理论和基本方法，具备解决图论问题的基本知识的能力。2.通过本课程学习，学生理解图论的思想方法，提高分析问题和解决问题的能力，从而培养学生的数学素养。3.通过本课程学习，学生能够掌握图论问题分析与论证技巧，解决实际

3、中的问题。4.通过本课程学习，学生具备处理中学教学中的相关问题的能力，具有终身学习和职业发展意识。毕业要求毕业要求指标点课程目标1课程目标2课程目标3课程目标4毕业要求3毕业要求指标点3.2MMLL毕业要求4毕业要求指标点4.1LLLL课程目标对毕业要求的支撑关系表三、教学内容与预期学习成效知识单元对应课程目标知识点预期学习成效实现环节学时1. 图与子图课程目标1、2、31.图与简单图2.图的同构3.关联与邻接矩阵4.子图5.顶点度6.路和连通7.圈1.掌握图与子图的相关概念2.掌握图的相关度、关联邻接阵、同构相关概念3.知道图的顶点与边的一些关联关系1.课堂教学2.课堂讨论6学时课程思政：通

4、过对图论的基本概念的介绍，让学生了解具体到抽象的变化，从而体会到数学的魅力，引发学生借助数学方法描述和解决实际生活中具体问题的兴趣。2. 树课程目标1、2、3树割边与键Cayley公式掌握树的基本概念和基本结论知晓割边的概念及相关结论了解键、Cayley公式的定义，并会计算生成树1.课堂教学4学时课程思政：树是一类最小连通图，具有一些较好的性质，在图论中具有特殊的地位。通过本章学习，能让学生弄清楚简单与复杂之间的辩证关系。3. 连通度课程目标1、2连通性块熟练判断一个图的顶点与边连通度了解块的定义及块的思想1.课堂教学2学时课程思政：通过本章学习，能让学生弄清楚一个图的顶点与边连通度的关系，让

5、学生体会到事物是普遍联系的。4. 欧拉环游与哈密尔顿圈课程目标1、2、3、4欧拉环游哈密尔顿圈掌握欧拉图定义及判定定理掌握哈密顿图的定义及判定的一些条件了解此两类图的历史背景及实际中的一些应用1.课堂教学6学时课程思政：通过本章学习，能让学生弄清欧拉环游和哈密尔顿问题的发展历史，激发学生的文化自信与民族自豪感，培养学生的严谨思维。5. 对集课程目标1、2、4对集偶图的对集与覆盖完美对集掌握对集的概念针对二部图的定义，掌握二部图匹配的特征了解完美匹配问题的充分必要条件1.课堂教学4学时课程思政：匹配理论在现实生活中有很强的实际背景和应用价值。通过本章学习，培养学生的创新思维能力。6. 边着色课程

6、目标1、2边着色数Vizing定理了解图的色类与边着色的相关概念与着色的思想了解Vizing定理中的关于边色数的相关结构1.课堂教学2.课堂讨论2学时课程思政：了解图的着色理论，可以让学生理解从一般到特殊的数学抽象概括能力。激发学生的求知欲与对数学家的敬仰之情，培养学生的探究精神与创新思维。8. 顶点着色课程目标1、2、4色数色多项式知道顶点着色的相关概念及重要结论会求着色多项式1.课堂教学2.课堂讨论4学时课程思政：了解图的着色理论，可以让学生理解从一般到特殊的数学抽象概括能力。激发学生的求知欲与对数学家的敬仰之情，培养学生的探究精神与创新思维。9. 平面图课程目标1、2、4平面图对偶图欧拉

7、公式掌握平面图的定义及其特殊图的判断方法了解对偶图定义，会计算一个图的面会证明欧拉公式，了解其在平面图着色中的作用1.课堂教学4学时课程思政：平面理论的历史发展，凸显了数学的内在美和和谐美，让学生充分认识数学对社会的作用。成绩评定及考核方式知识单元对应课程目标考核方式成绩评定1、 图与子图课程目标1、2、4平时表现+课堂训练+学期总结成绩评定方法如下： （1）平时作业依据作业态度，占总学期成绩的10%； （2）平时表现依据课堂的积极性，是否玩手机，听课态度，考勤等占总学期成绩的40%； （3）笔记学期结束上交，依据其记录的态度、完整性，占总学期成绩的20%。（4） 学期总结（可就某课题综述，或测试）占30%2、树课程目标1、2、3平时表现+课堂训练+学期总结3、连通度课程目标1、2平时表现+课堂训练+学期总结4、欧拉环游与哈密尔顿圈课程目标1、2、4平时表现+课堂训练+学期总结5、对集课程目标1、2平时表现+课堂训练+学期总结6、边着色课程目标1、2、4平时表现+课堂训练+学期总结8、顶点着色课程目标1、2、4平时表现+课堂训练+学期总结9、平面图课程目标1、2平时表现+课堂训练+学期总结五、课程建议教材及主要参考资料1. 建议教材 J.A.