获得北京市高校第五届青年教师教学基本功比赛最佳教案奖
北京高校第五届
青年教师教学基本功比赛
参赛教案
类 别 A组理工类 任课教师 岳瑞锋
第六章 图论 §1 图的基本概念
北京高校第五届 青年教师教学基本功比赛
课程名称 授课章节 授课对象 授课时间 50任课教师 参赛教案
运筹学
第六章 图论 §1 图的基本概念 非数学专业本科二年级 分钟 岳瑞锋
1
第六章 图论 §1 图的基本概念
1． 【教学目标】
1) 知识层面：通过七桥问题掌握欧拉定理，并利用中国邮路问题理解欧拉
定理在解决实际问题中的作用。掌握关于图的一些基本概念和结论。 2) 能力层面：通过解决七桥问题和中国邮路问题，培养学生将实际问题加
以抽象、建立一般模型的能力。学习利用数学知识，分析和解决模型，并最终回到实际问题。
3) 认知层面：体会图论中对图的讨论和传统几何学的不同之处，认识到对
图的这种分析角度打开了一个新的视野。
2． 【教学内容】
1) 七桥问题与欧拉定理。 2) 中国邮路问题的解法。 3) 图的基本概念和结论。
3． 【教学重点与难点】
1) 教学重点：欧拉定理，中国邮路问题，图的有关概念。
处理方法：重点讲解；启发主动思考；提供学生参与机会。 2) 教学难点：中国邮路问题算法过程；关于图的三个定理。
处理方法：根据学生反应，把握讲解速度；结合多媒体课件；利用提问
方式，随堂检验学生掌握程度。
4． 【教材分析】
图与网络分析是运筹学的重要内容之一。它以图为研究对象。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论是研究事物对象在上述表示法中具有的特征与性质的学科。图论的研究发源于18世纪普鲁士的柯尼斯堡。从19世纪中叶开始，图论问题大量出现。比如哈密顿问题、四色问题以及与之相关联的图的可平面性问题等。1936年D.柯尼希发表了图论的第一本专著《有限与无限图理论》，这时图论才成为一门学科。近代以来，由于生产管理、军事、交通运输和计算机网络等方面出现了大量实际问题，特别是许多离散化问题的出现，以及由于大型高速电子计算机而使许多大规模问题求解成为可能，图论的理论及其应用研究得到飞速发展。尤其是图论与线性规划、动态规划等优化理论和方法的互相渗透，促使和丰富了图论的内容和应用。
本次课是图论的第一节内容。由于图论直接从现实问题入手，经过抽象构建一般理论。对学生而言，除了比较基础的线性代数知识外，对其他分支的数学内容要求不高。但由于图论中对图的分析视角完全不同于传统几何学，从认知水平上，属于全新的认识角度。为了构建这门学科体系，学习图论之初要涉及大量的概念和定义，这将使得本来生动活泼的图论显得枯燥乏味。为了能够引起学生的学习兴趣，可从图论上的一些经典的问题入手，在此基础上，逐步引入重要的概念和结论，为后续的有关图的一些算法做准备。例如用七桥问题和中国邮路问题引入课程内容，逐步引导学生从实际问题中抽象出一般的图，并体会如何通过对图的讨论来解决现实问题。
本部分内容一方面具有较为直观的意义，另一方面，如果上升为数学上
2
第六章 图论 §1 图的基本概念
的一般结论，又不得不借助于大量的符号语言和逻辑推理。在教学过程中，应恰当处理借助图形直观含义和严密的数学推理之间的关系。既要引导学生从直观上发现问题的实质，也要注意对某些关键的结论进行缜密的逻辑推理。例如欧拉定理和中国邮路问题的算法过程的直观意义相当明显，但要进行数学证明则需要借助许多相关的概念和结论，证明过程反而掩盖了其数学本质，这时候就不易进行数学证明。
5． 【设计思路】
1) 设计要点一：
通过介绍七桥问题引入本课内容，一方面有助于引起学习兴趣，另一方面通过介绍七桥问题，使学生初步体会认识图的新视角。
设计依据：
创设问题情境，引起注意和好奇心理，是激发学习动机，进行有效学习的重要因素。
2) 设计要点二：
利用中国邮路问题阐述欧拉定理的应用，进一步体会图论和传统几何学对图的分析视角的重要区别。在完成中国邮路问题的算法过程之后，引导学生自主分析这种区别并进行归纳，从而完成从直观感觉到认知水平的升华。
设计依据：
学习的过程不仅仅简单掌握方法，更重要的是原有知识的重新体认，是认知结构的重塑和提升。 3) 设计要点三：
七桥问题和中国邮路问题的解决过程都遵循了“实际问题—建立模型—分析模型—解决问题”的思维方式。通过这种方式的教学，在潜移默化中培养学生利用已有知识解决现实问题的能力。
设计依据：
授课过程不仅要传授知识，而且要注重能力的培养。 4) 设计要点四：
上述两个问题有助于让学生认识到“图论既有意思也很有用处”，从而激发其求知欲望，这时恰当把握时机，将求知欲望转为学习动力，完成从“现实问题”到“数学理论”的升华，转入下一部分图的基本概念和结论。
设计依据：
每节课都有其内在的旋律，掌控其起承转合才能把握学生心理。适当情景下的转折是提升课堂内容水平的关键。
6． 【教学模式和手段】
1) 教学模式：问题导入——启发思考——共同分析——构建知识。 2) 教学手段：动态多媒体课件和板书结合。
7． 【板书设计，教学大纲，参考文献】
见附件。
8． 【教学过程】
3
第六章 图论 §1 图的基本概念
教学步骤 教学内容 设计意图 表达方式 一、引例：七桥问题(10分钟) 在哥尼斯堡镇(Konigsberg)的旁边有一条河流，河中有两个小岛，通过7座桥梁相连。有人提出这样一个问题：能不能不重不漏的走过每一座桥梁，并且再回到起点？有人写信请教当时在利用多媒彼得堡科学院任院士的数学家欧拉，请他帮助解体课件， 1．提出问决这个问题。 介绍问题题，导入背景，用本课内问题激发容。 学生兴趣。 图1-1 1． 建立模型 首先，欧拉试图将这个问题做一些抽象，将河的两岸和两个小岛分别看成点，将七座桥看成点之间的连线，于是，七桥问题就抽象为下列问题： “在图1-2中，能不能从某点出发，不重不漏的走过每一条边，再回到起点？” D 2．分析问题特征，总结得到欧拉定理，并利用欧拉定理解决七桥问题。 A C 将问题加以抽象，建立一般模型，在此过程中注意提醒学生思考问题的解决方法。 课件演示 B 利用课件中的图，学习这几个概念。 启发学生思考奇偶顶点的区别。 图1-2 2． 解决问题的准备——几个概念 (1). 图(Graph)：一个图G包含两种元素:顶点集合V(Vertex)和边集合E(Edge)，即G={V,E}。 (2). 路(path)：在图中，若干条边相连，形成路。 (3). 连通图(connected graph)：任意两点之间都有路相连的图。 A B 图1-3
4