获得北京市高校第五届青年教师教学基本功比赛最佳教案...

获得北京市高校第五届青年教师教学基本功比赛最佳教案奖北京高校第五届参赛教案类别A组理工类任课教师岳瑞锋青年教师教学基本功比赛第六章图论§1图的基本概念1北京高校第五届青年教师教学基本功比赛参赛教案课程名称运筹学授课章节第六章图论§1图的基本概念授课对象非数学专业本科二年级授课时间50分钟任课教师岳瑞锋第六章图论§1图的基本概念21．【教学目标】1)知识层面：通过七桥问题掌握欧拉定理，并利用中国邮路问题理解欧拉定理在解决实际问题中的作用。掌握关于图的一些基本概念和结论。2)能力层面：通过解决七桥问题和中国邮路问题，培养学生将实际问题加以抽象、建立一般模型的能力。学习利用数学知识，分析和解决模型，并最终回到实际问题。3)认知层面：体会图论中对图的讨论和传统几何学的不同之处，认识到对图的这种分析角度打开了一个新的视野。2．【教学内容】1)七桥问题与欧拉定理。2)中国邮路问题的解法。3)图的基本概念和结论。3．【教学重点与难点】1)教学重点：欧拉定理，中国邮路问题，图的有关概念。处理方法：重点讲解；启发主动思考；提供学生参与机会。2)教学难点：中国邮路问题算法过程；关于图的三个定理。处理方法：根据学生反应，把握讲解速度；结合多媒体课件；利用提问方式，随堂检验学生掌握程度。4．【教材分析】图与网络分析是运筹学的重要内容之一。它以图为研究对象。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论是研究事物对象在上述表示法中具有的特征与性质的学科。图论的研究发源于18世纪普鲁士的柯尼斯堡。从19世纪中叶开始，图论问题大量出现。比如哈密顿问题、四色问题以及与之相关联的图的可平面性问题等。1936年D.柯尼希发表了图论的第一本专著《有限与无限图理论》，这时图论才成为一门学科。近代以来，由于生产管理、军事、交通运输和计算机网络等方面出现了大量实际问题，特别是许多离散化问题的出现，以及由于大型高速电子计算机而使许多大规模问题求解成为可能，图论的理论及其应用研究得到飞速发展。尤其是图论与线性规划、动态规划等优化理论和方法的互相渗透，促使和丰富了图论的内容和应用。本次课是图论的第一节内容。由于图论直接从现实问题入手，经过抽象构建一般理论。对学生而言，除了比较基础的线性代数知识外，对其他分支的数学内容要求不高。但由于图论中对图的分析视角完全不同于传统几何学，从认知水平上，属于全新的认识角度。为了构建这门学科体系，学习图论之初要涉及大量的概念和定义，这将使得本来生动活泼的图论显得枯燥乏味。为了能够引起学生的学习兴趣，可从图论上的一些经典的问题入手，在此基础上，逐步引入重要的概念和结论，为后续的有关图的一些算法做准备。例如用七桥问题和中国邮路问题引入课程内容，逐步引导学生从实际问题中抽象出一般的图，并体会如何通过对图的讨论来解决现实问题。本部分内容一方面具有较为直观的意义，另一方面，如果上升为数学上第六章图论§1图的基本概念3的一般结论，又不得不借助于大量的符号语言和逻辑推理。在教学过程中，应恰当处理借助图形直观含义和严密的数学推理之间的关系。既要引导学生从直观上发现问题的实质，也要注意对某些关键的结论进行缜密的逻辑推理。例如欧拉定理和中国邮路问题的算法过程的直观意义相当明显，但要进行数学证明则需要借助许多相关的概念和结论，证明过程反而掩盖了其数学本质，这时候就不易进行数学证明。5．【设计思路】1)设计要点一：通过介绍七桥问题引入本课内容，一方面有助于引起学习兴趣，另一方面通过介绍七桥问题，使学生初步体会认识图的新视角。设计依据：创设问题情境，引起注意和好奇心理，是激发学习动机，进行有效学习的重要因素。2)设计要点二：利用中国邮路问题阐述欧拉定理的应用，进一步体会图论和传统几何学对图的分析视角的重要区别。在完成中国邮路问题的算法过程之后，引导学生自主分析这种区别并进行归纳，从而完成从直观感觉到认知水平的升华。设计依据：学习的过程不仅仅简单掌握方法，更重要的是原有知识的重新体认，是认知结构的重塑和提升。3)设计要点三：七桥问题和中国邮路问题的解决过程都遵循了“实际问题—建立模型—分析模型—解决问题”的思维方式。通过这种方式的教学，在潜移默化中培养学生利用已有知识解决现实问题的能力。设计依据：授课过程不仅要传授知识，而且要注重能力的培养。4)设计要点四：上述两个问题有助于让学生认识到“图论既有意思也很有用处”，从而激发其求知欲望，这时恰当把握时机，将求知欲望转为学习动力，完成从“现实问题”到“数学理论”的升华，转入下一部分图的基本概念和结论。设计依据：每节课都有其内在的旋律，掌控其起承转合才能把握学生心理。适当情景下的转折是提升课堂内容水平的关键。6．【教学模式和手段】1)教学模式：问题导入——启发思考——共同分析——构建知识。2)教学手段：动态多媒体课件和板书结合。7．【板书设计，教学大纲，参考文献】见附件。8．【教学过程】第六章图论§1图的基本概念4教学步骤教学内容设计意图表达方式1．提出问题，导入本课内容。一、引例：七桥问题(10分钟)在哥尼斯堡镇(Konigsberg)的旁边有一条河流，河中有两个小岛，通过7座桥梁相连。有人提出这样一个问题：能不能不重不漏的走过每一座桥梁，并且再回到起点？有人写信请教当时在彼得堡科学院任院士的数学家欧拉，请他帮助解决这个问题。图1-1利用多媒体课件，介绍问题背景，用问题激发学生兴趣。2．分析问题特征，总结得到欧拉定理，并利用欧拉定理解决七桥问题。1．建立模型首先，欧拉试图将这个问题做一些抽象，将河的两岸和两个小岛分别看成点，将七座桥看成点之间的连线，于是，七桥问题就抽象为下列问题：“在图1-2中，能不能从某点出发，不重不漏的走过每一条边，再回到起点？”图1-2将问题加以抽象，建立一般模型，在此过程中注意提醒学生思考问题的解决方法。课件演示2．解决问题的准备——几个概念(1).图(Graph)：一个图G包含两种元素:顶点集合V(Vertex)和边集合E(Edge)，即G={V,E}。(2).路(path)：在图中，若干条边相连，形成路。(3).连通图(connectedgraph)：任意两点之间都有路相连的图。图1-3利用课件中的图，学习这几个概念。启发学生思考奇偶顶点的区别。BAABBCCDDA第六章图论§1图的基本概念5教学步骤教学内容设计意图表达方式(4).奇顶点和偶顶点(oddvertexandevenvertex)：如果从某个顶点出发的边数是奇数，称这个顶点为奇顶点；否则称为偶顶点。注意：奇偶顶点的分类，对于解决七桥问题至关重要。欧拉的结论：(1)起点和终点不是同一点：只能有两个奇顶点。如图1-4。(2)起点和终点是同一点：不能有奇顶点。如图1-5。图1-4图1-5欧拉定理：连通图可以不重不漏走过每一条边的充分必要条件是图的奇顶点的个数为0或2，并且，当且仅当奇顶点的个数为0时，可以回到起点。结合学生讨论，总结欧拉定理。利用动画演示行进路线。3．解决七桥问题：在图1-2中，由于4个顶点均为奇顶点，所以，不存在不重不漏的走过每一条边并回到起点的走法。实际上，根据欧拉定理，即使不要求回到起点，也不存在不重不漏的走法。从实际问题出发，还要回到实际问题中来。4．知识扩展：1921年，Fleury给出了欧拉回路的一般算法，详细资料可参见延伸课堂内容，供学有余力的同学拓展知识面。二、欧拉定理的应用—中国邮路问题(15分钟)问题描述：邮递员送信，怎样安排路线使他以最短距离走遍每个街道，最后再回到起点？背景介绍：由山东师范大学的管梅谷于1962年提出并解决，所以被称为中国邮路问题。根据杜威的学习观，必须经过检验才能获得新知识。ACDBACDB第六章图论§1图的基本概念6教学步骤教学内容设计意图表达方式3．利用欧拉定理解决中国邮路问题。1．建立模型：像解决七桥问题那样，将送信问题抽象为图。在图1-6中，顶点K表示邮局所在位置，边上的数字表示每一条街道的长度，邮递员需要从K出发，走遍每一条边之后，再回到K。从而问题转化为：给定一个具有非负权的图G，求G的一个Euler赋权母图G*，使得)(\)(*)(GEGEeew尽可能小。图1-6与七桥问题类似，同样采用“问题—抽象—解决”的过程，目的是为了培养学生解决问题的能力。课件演示课堂讨论：如果图中不存在奇顶点，根据欧拉定理，必存在不重不漏并且回到起点的走法，这种走法就是问题的最优方案。但如果图中存在奇顶点呢？问题1：在1-6图中，是否存在不重不漏的走法？为什么？结论：根据欧拉定理，不存在。这意味着，要想走遍每条街道，某些街道必须重复。问题2：直观上看，应该重复哪些街道，才可以使得总路程最短？结论：应该重复那些比较短的街道。问题3：那么该如何实现这种想法？（不形成结论，转入下一部份）结合课件演示，提出问题，引起讨论，启发学生思考。注意引导学生的讨论方向。AABBCCDDEEFFGGHHIIJJKK00..8800..4400..4411..22第六章图论§1图的基本概念7教学步骤教学内容设计意图表达方式2．分析问题：已经知道：第一，必定要重复走过某些街道。第二，最好重复走那些比较短的街道。在图中，可以用添加边的方式表示重复走的那些街道。如图1-7，表示计划重走H-K街道。图1-7摆脱实际问题背景，直接从图上分析。课件演示3．加边原则：原则1：加边是为了去掉途中的奇顶点。因为根据欧拉定理，只有在图中不存在奇顶点时，才存在不重不漏并且回到起点的走法。问题：如果按图1-8的形式加边，能不能保证总路程最短？图1-8结论：不能，因为可以在圈中加另外的边。原则2：每个圈上所加的边长之和不能超过圈的一半。问题：怎样加边才可以使得总路程减少？结论：如果某个方案在某个圈上所加的边长超过圈长的一半，则应该改进。原则3：如果超过,则去掉原来所加的边,在圈中剩余路线上加边。总结：加边的这三个原则就可以使得即减少了奇顶点的数目，又可以使得总路程最短。结合课件，依次提出问题，师生共同参与讨论，归纳三原则。AABBCCDDEEFFGGHHIIJJKK00..8800..4400..4411..2200..66AABBCCDDEEFFGGHHIIJJKK00..8800..4400..4411..2200..66第六章图论§1图的基本概念8教学步骤教学内容设计意图表达方式4．解决问题：1)寻找初始可行方案（FeasibleScheme）。在图1-6中，任意确定一种加边方式。如图1-9。图1-92)方案的迭代（iteration）。由于在圈ABJKHIA中，所加边的总长超过圈长的一半，根据加边原则，去掉所加边AI，AB，HK。用边HI，BJ，JK迭代。得到图1-10。图1-103)得到最优方案（OptimalScheme）。在图1-10中，不再含有奇顶点，并且每一个圈上所加的边长总合不超过圈长的一半。于是如图1-11所示的行进方式就是邮递员走过每一条街道，回到邮局的最佳路线之一。图1-11根据加边原则，解决中国邮路问题。体会初始解和解的迭代思想。动画演示最优方案AABBCCDDEEFFGGHHIIJJKK00..8800..4400..4411..2200..66AABBCCDDEEFFGGHHIIJJKK00..8800..4400..4411..2200..66AABBCCDDEEFFGGHHIIJJKK00..8800..4400..4411..2200..66第六章图论§1图的基本概念9教学步骤教学内容设计意图表达方式总结：以上通过对图的讨论解决了七桥问题和中国邮路问题。和传统几何学一样，现在也是在讨论和分析一些几何图形，但是分析的方法和视角和传统几何学却不一样。这是七桥问题的意义所在。小结并过渡，完成课堂内容的转折。5．知识扩展：中国邮路问题是NP难度问题。上述算法过程中，在每一次方案迭代时都要检查每个圈，当图较为复杂时，算法的效率很低。1973年，著名的组合数学家J.Edmonds和J