第六章 图论 §1 图的基本概念
教学步骤 教学内容 (4). 奇顶点和偶顶点(odd vertex and even vertex)： 如果从某个顶点出发的边数是奇数，称这个顶点为奇顶点；否则称为偶顶点。 注意：奇偶顶点的分类，对于解决七桥问题至关重要。 欧拉的结论： (1) 起点和终点不是同一点：只能有两个奇顶点。如图1-4。 (2) 起点和终点是同一点：不能有奇顶点。如图1-5。 A D 设计意图 表达方式 B C 图1-4 A D 结合学生讨论，总结欧拉定理。 利用动画演示行进路线。 B C 图1-5 欧拉定理：连通图可以不重不漏走过每一条边的充分必要条件是图的奇顶点的个数为0或2，并且，当且仅当奇顶点的个数为0时，可以回到起点。 3． 解决七桥问题： 在图1-2中，由于4个顶点均为奇顶点，所以，不存在不重不漏的走过每一条边并回到起点的走法。实际上，根据欧拉定理，即使不要求回到起点，也不存在不重不漏的走法。 4． 知识扩展： 1921年，Fleury给出了欧拉回路的一般算法，详细资料可参见http://www.algorithmist.com/ 从实际问题出发，还要回到实际问题中来。 延伸课堂内容，供学有余力的同学拓展知识面。
二、欧拉定理的应用—中国邮路问题(15分钟) 的学习问题描述：邮递员送信，怎样安排路线使他以最短距离走遍每个街道，最后再回到起点？ 背景介绍：由山东师范大学的管梅谷于1962年提出并解决，所以被称为中国邮路问题。 5
根据杜威观，必须经过检验才能获得新知识。 第六章 图论 §1 图的基本概念
教学步骤 3．利用欧拉定理解决中国邮路问题。 教学内容 1． 建立模型： 像解决七桥问题那样，将送信问题抽象为图。在图1-6中，顶点K表示邮局所在位置，边上的数字表示每一条街道的长度，邮递员需要从K出发，走遍每一条边之后，再回到K。从而问题转化为： 给定一个具有非负权的图G，求G的一个Euler赋权母图G*，使得?w(e)尽可能小。 e?E(G*)\\E(G)设计意图 表达方式 A I 0.4 H 0.8 B J K 1.2 C D E 0.4 与七桥问题类似，同样采用“问题—抽象—解决”的过程，目的是为了培养学生解决问题的能力。 课件演示 G F 图1-6 课堂讨论：如果图中不存在奇顶点，根据欧拉定理，必存在不重不漏并且回到起点的走法，这种走法就是问题的最优方案。但如果图中存在奇顶点呢？ 问题1：在1-6图中，是否存在不重不漏的走法？为什么？ 结论：根据欧拉定理，不存在。这意味着，要想走遍每条街道，某些街道必须重复。 问题2：直观上看，应该重复哪些街道，才可以使得总路程最短？ 结论：应该重复那些比较短的街道。 问题3：那么该如何实现这种想法？（不形成结论，转入下一部份） 结合课件演示，提出问题，引起讨论，启发学生思考。 注意引导学生的讨论方向。 6
第六章 图论 §1 图的基本概念
教学步骤 教学内容 2． 分析问题： 已经知道：第一，必定要重复走过某些街道。第二，最好重复走那些比较短的街道。在图中，可以用添加边的方式表示重复走的那些街道。如图1-7，表示计划重走H-K街道。 A I 0.4 H 0.6 G F 0.8 B J K 1.2 C D E 0.4 设计意图 表达方式 摆脱实际问题背景，直接从图上分析。 课件演示 图1-7 3． 加边原则： 原则1：加边是为了去掉途中的奇顶点。因为根据欧拉定理，只有在图中不存在奇顶点时，才存在不重不漏并且回到起点的走法。 问题：如果按图1-8的形式加边，能不能保证总路程最短？ A I 0.8 B J 1.2 C D 0.4 0.4 结合课件，依次K E H 提出问题，师生0.6 共同参与G F 讨论，归图1-8 纳三原结论：不能，因为可以在圈中加另外的边。 则。 原则2：每个圈上所加的边长之和不能超过圈的一半。 问题：怎样加边才可以使得总路程减少？ 结论：如果某个方案在某个圈上所加的边长超过圈长的一半，则应该改进。 原则3：如果超过,则去掉原来所加的边,在圈中剩余路线上加边。 总结：加边的这三个原则就可以使得即减少了奇顶点的数目，又可以使得总路程最短。
7
第六章 图论 §1 图的基本概念
教学步骤 教学内容 设计意图 表达方式 4． 解决问题： 1) 寻找初始可行方案（Feasible Scheme）。在图根据加边1-6中，任意确定一种加边方式。如图1-9。 原则，解决中国邮1.2 A 0.8 B C 路问题。 0.4 J D I 0.4 K E H 0.6 G F 图1-9 2) 方案的迭代（iteration）。由于在圈ABJKHIA 中，所加边的总长超过圈长的一半，根据加边体会初始原则，去掉所加边AI，AB，HK。用边HI，解和解的BJ，JK迭代。得到图1-10。 迭代思想。 1.2 B A 0.8 C 0.4 J D I 0.4 K E H 0.6 G F 图1-10 3) 得到最优方案（Optimal Scheme）。在图1-10 中，不再含有奇顶点，并且每一个圈上所加的 边长总合不超过圈长的一半。于是如图1-11动画演示所示的行进方式就是邮递员走过每一条街道，最优方案 回到邮局的最佳路线之一。 1.2 A 0.8 B C 0.4 J D I 0.4 K H E 0.6 G F 图1-11
8
第六章 图论 §1 图的基本概念
教学步骤 教学内容 总结：以上通过对图的讨论解决了七桥问题和中国邮路问题。和传统几何学一样，现在也是在讨论和分析一些几何图形，但是分析的方法和视角和传统几何学却不一样。这是七桥问题的意义所在。 5． 知识扩展： 中国邮路问题是NP难度问题。上述算法过程中，在每一次方案迭代时都要检查每个圈，当图较为复杂时，算法的效率很低。1973年，著名的组合数学家J. Edmonds和Johnson结合Fleury算法给出了解决一般邮路问题的更好的算法。对这个算法的详细资料可参考《算法分析导论》（作者Robert Sedgewick）。 设计意图 表达方式 小结并过渡，完成课堂内容的转折。 延伸课堂内容，供学有余力的同学拓展知识面。 三、七桥问题的意义(4分钟) 1．一种新的几何学——拓扑学(Topology)。 欧拉认识到，虽然七桥问题也是对图形的讨论，但是现在的视角和传统的几何学不同。初等几何研究的是在刚性变换下的图形的不变性质，如长度、角度、面积。射影几何研究的是在射影变化下图形的不变性质，如点、直线和交比。现在关注的是图形的顶点和边之间的关联和邻接关系是否存在。这种新的视角促进了一种新的几何学——拓扑学的诞生。拓扑学研究的是在拓扑变换下图形的不变性质。由于一个圆可以经过连续的变换，得到一个三角形，所以在拓扑学看来，圆和三角形就是拓扑等价的。 4．总结上述两个问题的解决过程，引导学生以新的视角来认识图。 结合课件概括介绍拓扑学，但本部分不是本课的核心，只是提供一个思考的视角，意义2才是本部分的目的。 图1-12 2．图论的产生。 因为拓宽了数学的视野，所以对图的讨论在数学理论上有着重要的意义，同时随着对图的深入研究，人们逐渐认识到，许多现实生活中的问题都可以经过抽象而最终归结一个图。比如运输问题，网络流量问题，最优的生产安排问题等等。而研究如何通过对图的讨论解决现实中的一些优化问题，就是现在要学习的运筹学的分支——图论的研究内容。 这部分即是课堂的又一个转折点，也是课堂内容的升华。 9