1、长沙民政职业技术学院教案课程名称数学应用基础课题欧拉图及其应用授课课时2课型新授课教案编号 4-2 教学目标（知识、技能、素质）：1、 知识目标：掌握欧拉路、欧拉回路及欧拉图、半欧拉图的概念和判定方法；掌握欧拉图的应用；Fleury算法；2、技能目标：分析解决问题的能力和严谨的逻辑思维能力3、素质目标：培养学生理性的思维方式和数学应用意识教学重点： 欧拉路、欧拉回路及欧拉图的判定；欧拉图的应用；利用 Fleury算法寻找欧拉回路；教学难点：欧拉图的判定及其应用主要教学方法：启发引导式、讲授法教学环节与内容一、问题引入引例1 (设计区间公交车路线)某运输管理部门在设计一个新的区间公交系统，来运送
2、城市商业区的顾客,具体地图如图4-10所示，为了提高公交车的运行效率，他们希望能够设计一条恰好通过商业区每条道路一次的运行路线，并且最终回到初始位置。图4-10 商业区地图为此，首先将每一个道路交叉口用一个顶点表示，连接两个交叉口的道路用一条边表示，这样我们就可以将地图模拟成图4-11所示。图4-11 商业区模拟图从而将问题转化为在图4-11中找到一条从顶点A出发，走遍图中每条边一次且仅一次的回路。二、新课讲授定义1 经过图中所有边一次且仅一次的路称为欧拉路。起点和终点是同一顶点的欧拉路称为欧拉回路。包含欧拉回路的图称为欧拉图，包含欧拉路但不包含欧拉回路的图称为半欧拉图。例如，在图4-12中，
3、路径ABCDEFBEA包含了图中的所有边，并且路径中没有重复的边，所以路径 ABCDEFBEA是一条长度为8的欧拉路，它也是一条欧拉回路，因为它的起点和终点都在同一个顶点。图4-12注意：欧拉图肯定包含欧拉路和欧拉回路，半欧拉图只包含欧拉路而不包含有欧拉回路。定义2 一个顶点所关联的边(即以该顶点为端点的边)的条数，称为该顶点的度数。例如，在图4-13中，顶点A、B、D、E、F的度数均为2，因为与这些顶点关联的边都是两条。类似地，因为与顶点C、G相连的边为3条，所以顶点C、G的度数为3。图4-13定义3 度数为奇数的顶点称为奇顶点，度数为偶数的顶点为偶顶点。如，在图4-13中，顶点A、B、D、
4、E、F是偶顶点，顶点C、G是奇顶点。案例1 判断图4-13能否在笔不离纸的情况下一笔画出来。解 在画图的过程中，采取走过一条边就擦掉这条边的方式，如果能把所有边都擦掉，那么这个图肯定就能够一笔画出来。也就是说，图中所有顶点的度数都要变为0，因为如果还存在度数不为0的顶点，那么肯定还有边没被擦掉。假设从顶点C出发，沿着边CD走到顶点D，并把边CD擦掉，如图4-14（a），顶点C和顶点D的度数都减少了1。接着，从顶点D出发到达顶点A，顶点D的度数又减少了1，故顶点D的度数变为0，如图4-14（b），我们已走的路是CDA。图4-14事实上，在一笔画过程中，每经过一个顶点，该顶点的度数都要减2，因此，
5、不管经过顶点几次，经过的顶点的奇偶性不变，即偶顶点还是偶顶点，奇顶点还是奇顶点。一个图能否被一笔画出来，只需要看各顶点是否都是偶顶点(出发点和结束点除外)。在本例中，我们继续从A出发，经过B点，到达顶点C，此时所走的路是CDABC。然后，从C点出发依次经过顶点G、F、E，再回到G点，所走的路为CDABCGFEG。至此，图中所有边都被擦掉了，图4-13能够一笔画出来。欧拉图判定定理 一个图G是欧拉图的充分必要条件是图G是连通图且无奇顶点。半欧拉图判断定理 一个图G是半欧拉图的充分必要条件是图G是连通图且刚好有两个奇顶点。半欧拉图对应的欧拉路必定以两个奇顶点为端点。案例2 (蚂蚁比赛问题)甲、乙两
6、只蚂蚁分别位于顶点A、B处。假设图中边的长度是相等的，甲、乙进行比赛，从它们所在顶点出发，走遍图中的所有边，最后到达顶点C。如果它们的速度相同，请问谁先到达目的地？图4-16 蚂蚁比赛图解 图4-16中仅有两个奇顶点A、C，根据半欧拉图判定定理，存在从A到C的欧拉路，蚂蚁甲走到C只需要走一条欧拉路，边数为9条。而蚂蚁乙要想走完所有的边到达C，至少要先走一条边到达A，再走一条欧拉路，故蚂蚁乙至少要走10条边才能到达C点，因此，在速度相同的情况下，蚂蚁甲先到达目的地。现在我们已经能确定图4-11是一个欧拉图，因此，公交车路线设计问题中管理部门希望的设计路线一定是存在的，剩下的事情就只需要在图中找到
7、这样一条路线即可。我们如何在一个比较复杂的图中找到一条欧拉回路呢？Fleury(弗罗莱)给出了一个系统寻找欧拉回路的算法。Fleury算法 在一个欧拉图中，我们可以按照下面的步骤寻找欧拉回路：从图中任意一个顶点开始，运用下面的规则连续地通过各边：（1）经过一条边后，把它擦掉。如果一个顶点的所有边都被擦掉，那么也将这个顶点擦掉。（2）当且仅当没有其他的选择时经过一座桥。例10 利用Fleury算法在图4-11中寻找到一条欧拉回路。解 第一步：从顶点A开始，走过边AH，并把它擦掉。如图4-17所示。第二步：经过边HG和GF，到达F点。擦掉边HG和GF，而且所有连接顶点G的边都被擦掉了，所以把顶点G
8、也擦掉。目前的路是AHGF。如图4-18所示。第三步：经过边FE、ED、DC，并擦去它们和顶点E， 此时到达顶点C的路是AHGFEDC，如图4-19所示。第四步：现在边CB是一座桥，但是除了它没有别的选择，沿着边CB连续通过BD、DI、IF、FH、HI、IB、BA回到顶点A，最终的回路是AHGFEDCBDIFHIBA。如果运输管理部门沿着这条回路来设计公交车的运行路线，就可以每条路只走一次来提高运行效率。图4-17 图4-18 图4-19例11 一个邮递员投递信件要走的街道如图4-20所示，图中的数字表示各条街道的千米数，他从邮局A出发，要走遍各街道，最后回到邮局。怎样走才能使所走的行程最短？
9、全程多少千米？图4-20 街道示意图解 图中顶点B、D、E、F、G、H、I、J、K、L均是奇顶点，根据欧拉图判定定理，图4-20不是欧拉图。因此，邮递员要想把每条街道只走一遍然后回到邮局是不可能实现的，他必须重复走一些街道。如果邮递员想要行程最短，他重复走的街道数越少越好、越短越好。因为欧拉回路是一条通过图中每条边一次且仅一次的路，不存在行程的长短，所以问题转化为如何在图4-20中添加边，使添加的边的长度之和最短，且消除图4-20中所有的奇顶点。图4-20有10个奇顶点，至少添加5条边，故一个使长度之和最短的添加边的方案如图4-21所示。 图4-21接下来，我们可利用Fleury算法在图4.21中找到一条欧拉回路，比如ABCDJMLKNGHK LIHIJDEBEFGFA，这是一条邮递员行程最短的回路，最短行程为34千米。课后小记
