《图论及其应用》课程教学大纲 Graph Theory and Its Applications

《图论及其应用》课程教学大纲 课程名称：图论及其应用(Graph Theory and Its Applications) 课程编号：L12345 总学时数：32 讲课学时：32 实验学时：0 实践学时：0 上机学时：0 学分：2 先修课程：高等代数 教材：《图论及其应用》，张先迪李正良编，高等教育出版社，2005年第 1版 参考书目： [1]《图论》，王禾瑞编，科学出版社，2009年第2版： [2]《图论及其应用》，J.A邦迪，U.S.R.默蒂，科学出版社 [3]《图论及其应用》，卓新建、苏永美等编，北京邮电大学出版社，201 年第1版 课程内容筒介：图论是离散数学的主要分支之一，在现代科学技术中有着重要的 理论价值和广泛的应用背景，特别是在人工智能、大数据和网络科学的迅猛发展 背景下，日益受到重视并蓬勃发展！图论主要用图描述和表示事物以及事物与事 物之间的关系。本课程主要介绍图论的基本知识和学习方法，培养学生的离散思 维。 一、教学目标 1.知识目标 1.1了解图论的基本概念，理解并掌握树、匹配与覆盖、遍历问题、连通度 问题、着色问题、平面图、图与矩阵的基本内容。 1.2锻炼学习图论的离散思维，掌握解决图论问题的基本方法，熟悉图论在 现实生活和相关学科的应用。 2.能力目标 2.1通过本课程的学习，培养和提高学生离散与逻辑思维的能力。 2.2提高利用图论进行数学建模的能力，分析与解决实际问题的能力。 3.素质目标 3.1通过本课程的学习，培养数学学科素养，尤其在培养学生离散思维的素 养，数学研究的基本素质，理论联系实际，学以致用的数学精神。 3.2培养学生求真务实、严谨科学、锲而不舍的数学精神，建立科学的思想 方法

《图论及其应用》课程教学大纲 课程名称：图论及其应用（Graph Theory and Its Applications） 课程编号：L12345 总学时数：32 讲课学时： 32 实验学时：0 实践学时： 0 上机学时：0 学 分：2 先修课程：高等代数 教 材：《图论及其应用》，张先迪 李正良编，高等教育出版社，2005 年第 1 版 参考书目： [1]《图论》，王禾瑞编，科学出版社，2009 年第 2 版； [2]《图论及其应用》，J.A.邦迪，U.S.R. 默蒂，科学出版社 [3] 《图论及其应用》，卓新建、苏永美等编，北京邮电大学出版社，201 年第 1 版 课程内容简介：图论是离散数学的主要分支之一，在现代科学技术中有着重要的 理论价值和广泛的应用背景，特别是在人工智能、大数据和网络科学的迅猛发展 背景下，日益受到重视并蓬勃发展！图论主要用图描述和表示事物以及事物与事 物之间的关系。本课程主要介绍图论的基本知识和学习方法，培养学生的离散思 维。 一、教学目标 1．知识目标 1.1 了解图论的基本概念，理解并掌握树、匹配与覆盖、遍历问题、连通度 问题、着色问题、平面图、图与矩阵的基本内容。 1.2 锻炼学习图论的离散思维，掌握解决图论问题的基本方法，熟悉图论在 现实生活和相关学科的应用。 2．能力目标 2.1 通过本课程的学习，培养和提高学生离散与逻辑思维的能力。 2.2 提高利用图论进行数学建模的能力，分析与解决实际问题的能力。 3．素质目标 3.1 通过本课程的学习，培养数学学科素养，尤其在培养学生离散思维的素 养，数学研究的基本素质，理论联系实际，学以致用的数学精神。 3.2 培养学生求真务实、严谨科学、锲而不舍的数学精神，建立科学的思想 方法

4.情感目标 通过课程思政教育积极引导、培养师范生对教师职业的高度认同感与职业自 豪感。 二、课程目标与毕业要求的对应关系 教学目标 支排的毕业要求 支的毕业要求指标点 教学目标1.1 建构图论知识体系，培养学生扎实的数学基础，逻辑推 教学目标1.2 3.学科素养 理，离散数学的思维能力以及解决实际问题的能力，培 养学生跨学科整合知识研究问题的能力。 4.教学能力 使学生认识到教学过程中教师与学生的地位， 学科课程标准 够依据 学学科特点进行数学教学实践 通过课程学习使学生理解数学素养在育人过程中的作 教学目标2.1 教学目标2.2 掌握全 过程有人的万式万法，充分利用保室肉外 6.综合育人 校园内外的 从不同角度育人：能将全 到数学分 ,培养学生解 决实际同题的能 通过图论的教学与学习，培养学生离散数学思维、严密 7.学会反思 理能力、逻思考能力、数字批判思维和证维 决问题能力和创新意识，初步 教学目标3.1 备数学教学研究能力。 教学目标3.2 通过小组讨论建模实践等教学形式，培养学生交流合作 8.沟通合作 ,掌握沟通合作、分工协作意识 能够独立开展小组互助学习和合作学习的能力。 课程与毕业要求的关联度矩阵 业要求 课程 情怀 数学分析(B)I 注：表中误程体系：具体课程、实我环节，训练等：根据课程对各项毕业要求的支撑强度分 别用“H(高)”、 (中)” “L(弱)”表示该课程对毕业要求贡献度的大小。矩阵应覆 盖所有必修环节。 三、教学基本内容与课程目标对应关系 章节 教学内容与教学要求 戴学设计 与课程目标 课时 对应关系

4.情感目标 通过课程思政教育积极引导、培养师范生对教师职业的高度认同感与职业自 豪感。 二、课程目标与毕业要求的对应关系 教学目标 支撑的毕业要求 支撑的毕业要求指标点 教学目标 1.1 教学目标 1.2 3.学科素养 建构图论知识体系，培养学生扎实的数学基础，逻辑推 理，离散数学的思维能力以及解决实际问题的能力，培 养学生跨学科整合知识研究问题的能力。 教学目标 2.1 教学目标 2.2 4.教学能力 使学生认识到教学过程中教师与学生的地位，能够依据 学科课程标准和数学学科特点进行数学教学实践。 6.综合育人 通过课程学习使学生理解数学素养在育人过程中的作 用，掌握全过程育人的方式方法，充分利用课堂内外， 校园内外的各种实践活动，从不同角度育人；能将全程 育人与立体育人理念融入到数学分析教学实践中，积极 组织学生参加建模竞赛，培养学生解决实际问题的能力 和朴素刻苦的学习作风。 教学目标 3.1 教学目标 3.2 7.学会反思 通过图论的教学与学习，培养学生离散数学思维、严密 推理能力、逻辑思考能力、数学批判思维和辩证思维， 初步具有发现问题、解决问题能力和创新意识，初步具 备数学教学研究能力。 8.沟通合作 通过小组讨论建模实践等教学形式，培养学生交流合作 的意识与团队协作精神，掌握沟通合作、分工协作意识， 能够独立开展小组互助学习和合作学习的能力。 课程与毕业要求的关联度矩阵 课程 毕业要求 师德 规范 教育 情怀 学科 素养 教学 能力 班级 指导 综合 育人 学会 反思 沟通 合作 数学分析(B)Ⅰ M L 注：表中课程体系：具体课程、实践环节、训练等；根据课程对各项毕业要求的支撑强度分 别用“H(高)”、“M（中）”、“L(弱)”表示该课程对毕业要求贡献度的大小。矩阵应覆 盖所有必修环节。 三、教学基本内容与课程目标对应关系 章节 教学内容与教学要求 教学设计 与课程目标 对应关系 课时

1.图论课程简介 2.什么是图，图的同构 3.子图与运算 课程目标3. 第1章 4路和连酒性 1.问题驱动教学 5.图与偶图特征 课程目标3. 图的概 2.讲授为主，结 课程目标3.2 念 1.理解图的概念 课程目标6.】 3 2堂提图间构的本质 后练习 3.熟练堂得子图及其各种运算 4.掌握途径、路的概念 5,掌握连通关系是等价关系 6.掌握偶图的圈特征 1.树的概念与性质 2树的中 L.问题驱动教 3.生成树 2.探究式教学 课程目标3. 1。堂握树的几种等价定义 3.讲授为主 第2率 课程目标3. 2.掌握顶点的距离、离心率、直径 合学生自学 课程目标3.2 树 中心点以及图的中心等定义 4,小组讨论、习 果程目标6.1 3.掌握树的中心的性质 题课讲解与课 4.掌握生成树的递推公式 后练习 5.熟悉完全图生成树的公式 5.文献探索 6。自学求赋权图最小生成树的算法 . 割边、割点和块 讲授为主，结 课程目标3.1 第3章 .连通度 合学生自学 课程目标3.2 图的连 1.掌握制边、割点和块的定义及关系 3.小组讨论与课 果程目标32 2.掌握割点与块充要条件 后练习 果程目标6. 通度 3.掌握点边连通度之问的关系 4文献探索 Euler图 第4章 2.Hamilton图 1.问题驱动教学 课程目标3.1】 Euler图 2.讲授为主，结 1.掌握Euler定理 果程目标3.2 合学生自学 果程目标32 2.掌握Hamilton图的充分条件 3.小组讨论、习 Hamilto3.掌握Hamilton图的必要条件 课程目标6.】 n图 4.自学中国邮递员问题与旅行售货员 1.匹配 1.问题驱动教学 课程目标3.1 第5章 2.偶图的匹配与履益 2.讲授为主，结 里相目标32 匹配 Tutte定理与完美匹配 合学生自学 里程目标39 3 4. 匹配在矩阵论中的应用 小组讨论与课 课程目标6.】

第 1 章 图的概 念 1.图论课程简介 2.什么是图, 图的同构 3.子图与运算 4.路和连通性 5.圈与偶图特征 1.问题驱动教学 2.讲授为主，结 合学生自学 3.小组讨论与课 后练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 3 1.理解图的概念 2.掌握图同构的本质 3.熟练掌握子图及其各种运算 4.掌握途径、迹、路的概念 5.掌握连通关系是等价关系 6.掌握偶图的圈特征 第 2 章 树 1.树的概念与性质 2.树的中心 3.生成树 1.问题驱动教 2.探究式教学 3.讲授为主，结 合学生自学 4.小组讨论、习 题课讲解与课 后练习 5.文献探索 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 3 1.掌握树的几种等价定义 2.掌握顶点的距离、离心率、直径、半 径、中心点以及图的中心等定义 3.掌握树的中心的性质 4.掌握生成树的递推公式 5.熟悉完全图生成树的公式 6.自学求赋权图最小生成树的算法 第 3 章 图的连 通度 1. 割边、割点和块 2. 连通度 1.讲授为主，结 合学生自学 3.小组讨论与课 后练习 4.文献探索 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 3 1.掌握割边、割点和块的定义及关系 2.掌握割点与块充要条件 3.掌握点边连通度之间的关系 第 4 章 Euler 图 与 Hamilto n 图 1. Euler 图 2. Hamilton 图 1.问题驱动教学 2.讲授为主，结 合学生自学 3.小组讨论、习 题课讲解与课 后练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 2 1.掌握 Euler 定理 2.掌握 Hamilton 图的充分条件 3.掌握 Hamilton 图的必要条件 4.自学中国邮递员问题与旅行售货员 问题 第 5 章 匹配 1. 匹配 2. 偶图的匹配与覆盖 3. Tutte 定理与完美匹配 4. 匹配在矩阵论中的应用 1.问题驱动教学 2.讲授为主，结 合学生自学 3.小组讨论与课 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 3

1.掌握最大匹配的充要条件 后练习 2.掌握匹配与覆盖的关系 3.了解Tutter定理 4.自学最优匹配与匈牙利算法 5.熟悉匹配与其他问题的联 1.独立集和团 上.问题驱动教学 程目标31 第6章 2.Ramsey定理 2.讲授为主，结 课程目标3.2 合学生自学 Ramsey 果程目标3.2 2 1。独立集与覆盖，匹配与边覆苦 3.小组讨论与课 课程目标6.1 定理 之问的关系 后练习 2.了解Ransey数与定理 图的矩阵表示及特征 1,联系教师的利 2.图的特征值与谱 研项目 3.图Laplacian矩阵与生成树 ,以科 小题目的形式 课程目标3.1 第7章 1.掌握图余邻接矩阵、关联矩阵之问的 发学生的兴趣 课程目标3.2 图与矩 关系、以及图矩阵包含的图信愿 2讲授为主。结 果程目标3.2 2.熟练计算特殊图的特征值 合学生自学 课程目标6.1 3.掌握图特征值与特定图参数（直径】 3.小组讨论 之间关系 题课讲解与课 4.掌握利用图矩阵计算生成树的个数 后练习 1.图的边着色 1.联系数师的科 2.顶点着色 研项目，以科研 3色多项 小颗目的形式潮 课程目标31 第8章 发学生的兴趣 果程目标3 1堂提偶图的动色新 2.讲授为主， 图的着 2.掌握 课程目标3.2 合学生自学 色 摆色多项式的性质 课程目标6.1 3.小组讨论、习 4.掌提伴随多项式的性质 5.熟悉图多项式与图同构之问的关系 题课讲解与课后 6.自学着色的应用 练习 1平而图 对偶 1.探究式教学 3.平面图的判定 2.讲授为主，结 课程目标3.1 第9幸 4.五色定理与四色猜想 合学生自学 裸程目标3.2 3.小组讨论、习 平面图 裸程目标3.2 1.掌操平面图的禁本性质 题课讲解与课后 2.掌握Euler公式 课程目标6. 3.了解Kuratowski定理 练习 4.熟悉五色定理

1.掌握最大匹配的充要条件 2.掌握匹配与覆盖的关系 3.了解 Tutter 定理 4.自学最优匹配与匈牙利算法 5.熟悉匹配与其他问题的联系 后练习 第 6 章 Ramsey 定理 1.独立集和团 2.Ramsey 定理 1.问题驱动教学 2.讲授为主，结 合学生自学 3.小组讨论与课 后练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 2 1. 掌握独立集与覆盖，匹配与边覆盖 之间的关系 2. 了解 Ramsey 数与定理 第 7 章 图与矩 阵 1. 图的矩阵表示及特征 2. 图的特征值与谱 3. 图 Laplacian 矩阵与生成树 1.联系教师的科 研项目，以科研 小题目的形式激 发学生的兴趣 2.讲授为主，结 合学生自学 3.小组讨论、习 题课讲解与课 后练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 3 1.掌握图余邻接矩阵、关联矩阵之间的 关系、以及图矩阵包含的图信息 2.熟练计算特殊图的特征值 3.掌握图特征值与特定图参数（直径） 之间关系 4.掌握利用图矩阵计算生成树的个数 第 8 章 图的着 色 1.图的边着色 2.顶点着色 3.色多项式 1.联系教师的科 研项目，以科研 小题目的形式激 发学生的兴趣 2.讲授为主，结 合学生自学 3.小组讨论、习 题课讲解与课后 练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 4 1.掌握偶图的边色数 2.掌握 Brooks 定理 3.掌握色多项式的性质 4.掌握伴随多项式的性质 5.熟悉图多项式与图同构之间的关系 6.自学着色的应用 第 9 章 平面图 1.平面图 2.对偶图 3.平面图的判定 4.五色定理与四色猜想 1.探究式教学 2.讲授为主，结 合学生自学 3.小组讨论、习 题课讲解与课后 练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 3 1.掌握平面图的基本性质 2.掌握 Euler 公式 3.了解 Kuratowski 定理 4. 熟悉五色定理

1.有向图 1问瓶取动教学 2有向树 课程目标3. 3.有向路与有向圈 2.讲授为主，结 课程目标3.2 第10章 合学生自学 课程目标3.2 有向图 1.掌握有向图的矩阵表示 3.小组讨论与课 课程目标6.1 ,掌握有向图的连通性 后练习 3.了解有向树、有向圈、有向路 四、教学建议进度 《数学分析（®）I》没课课时分配表 章 节 讲课 习题课讨论课 实验其他 合计 第1章图的概念 第2章树 3 0 0 1 第3章图的连通度 2 0 0 0 第4章Euler图与Hamilton图 3 0 0 0 第5章匹配 2 0 0 0 第6章Ramsey定理 0 0 0 第7章图与矩阵 4 第8张图的着色 3 第9章平面图 3 1 第10章有向图 2 合计 28 4 0 00 32 五、教学方法 1.以课堂讲授为主，实施探究性教学与范例教学等模式，使学生掌握基本知 识、思想和方法。 2.开展问题驱动下的小组讨论。 3.配置适当的习题课，提高学生离散思维，培养抽象思维和逻辑推理能力。 4.设立课外答疑时间，利用网络教学平台提供课后思考问题及能力提升题 目

第 10 章 有向图 1.有向图 2.有向树 3.有向路与有向圈 1.问题驱动教学 2.讲授为主，结 合学生自学 3.小组讨论与课 后练习 课程目标 3.1 课程目标 3.2 课程目标 3.2 课程目标 6.1 2 1.掌握有向图的矩阵表示 2.掌握有向图的连通性 3.了解有向树、有向圈、有向路 四、教学建议进度 《数学分析(B)Ⅰ》授课课时分配表 章 节 讲课 习题课 讨论课 实验 其他 合计 第 1 章 图的概念 3 1 0 0 0 第 2 章 树 3 0 0 0 第 3 章 图的连通度 2 0 0 0 第 4 章 Euler 图与 Hamilton 图 3 1 0 0 0 第 5 章 匹配 2 0 0 0 第 6 章 Ramsey 定理 3 0 0 0 第 7 章 图与矩阵 4 1 第 8 张 图的着色 3 第 9 章 平面图 3 1 第 10 章 有向图 2 合 计 28 4 0 0 0 32 五、教学方法 1.以课堂讲授为主，实施探究性教学与范例教学等模式，使学生掌握基本知 识、思想和方法。 2.开展问题驱动下的小组讨论。 3.配置适当的习题课，提高学生离散思维，培养抽象思维和逻辑推理能力。 4.设立课外答疑时间，利用网络教学平台提供课后思考问题及能力提升题 目

5.鼓励学生开展第二课堂学习与研究，参加数学建模竞赛以提升分析问题和 解决实际问题的能力，参与教师的科研项目激发学生的兴趣和创新能力。 六、成绩考核方式 闭卷考试，平时成绩和期中考试占30%，期末考试占70%。 考核方式对课程目标的达成情况 课程目标 考核内容 考核占比(%) 考核方式 重点考察对图论中定义和基本性质的 课程目标3.1 掌握，主要涵盖图的连通性、树的基 1.课堂表现 课程目标3.2 本性质、点（边）连通度、匹配及其 2.平时作业 课程目标3.2 应用、图的点（边）着色、色多项式与 80% 3.期中考试 伴随多项式、独立集与覆盖、有向图 4.期未考试 的基本性质等 重点考察自学小节的读书笔记与理解 主要包括最短路的Dantjig标号法、最 课程目标6.1 小生成树的Kruskal算法、中国邮递员 1.读书笔记 问题（最优环游）的Fleury算法、旅 20% 2.建模活动 行售货员问题、最优分配与匈牙利算 法、着色的应用。 七、制定本大纲的有关说明 说明：本大纲适用对象为数学与应用数学专业（师范）本科生。 大纲执笔者：王建锋 大纲审定者：孙文华 分管教学负责人签字：王贵栋 编写时间：2020年1月17日

5.鼓励学生开展第二课堂学习与研究，参加数学建模竞赛以提升分析问题和 解决实际问题的能力，参与教师的科研项目激发学生的兴趣和创新能力。 六、成绩考核方式 闭卷考试，平时成绩和期中考试占 30%，期末考试占 70%。 考核方式对课程目标的达成情况 课程目标 考核内容 考核占比（%） 考核方式 课程目标 3.1 课程目标 3.2 课程目标 3.2 重点考察对图论中定义和基本性质的 掌握，主要涵盖图的连通性、树的基 本性质、点（边）连通度、匹配及其 应用、图的点(边)着色、色多项式与 伴随多项式、独立集与覆盖、有向图 的基本性质等 80% 1.课堂表现 2.平时作业 3.期中考试 4.期末考试 课程目标 6.1 重点考察自学小节的读书笔记与理解， 主要包括最短路的 Dantjig 标号法、最 小生成树的 Kruskal 算法、中国邮递员 问题（最优环游）的 Fleury 算法、旅 行售货员问题、最优分配与匈牙利算 法、着色的应用。 20% 1.读书笔记 2.建模活动 七、制定本大纲的有关说明 说明：本大纲适用对象为数学与应用数学专业（师范）本科生。 大纲执笔者：王建锋 大纲审定者：孙文华 分管教学负责人签字：王贵栋 编写时间：2020 年 1 月 17 日