【2017年整理】欧拉图和汉密尔顿图.ppt

此定理是必要条件，可以用来证明一个图不是汉密尔顿图。 如右图，取S={v1,v4}，则G-S有3个连通分支， 不满足W(G-S)≤|S|，故该图不是汉密尔顿图。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 离散数学Discrete Mathematics Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四章 几种特殊的图  4-1 欧拉图和汉密尔顿图 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4-1 欧拉图和汉密尔顿图 要求： 1、理解欧拉图、汉密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是汉密尔顿图。 4、熟悉一些欧拉图和汉密尔顿图。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 学习本节要熟悉如下术语（9个）： 欧拉路、 欧拉图、 欧拉回路、 掌握6个定理，1个推论。 单向欧拉路、 单向欧拉回路、 汉密尔顿路、 汉密尔顿回路、 汉密尔顿图、 图的闭包 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 一、欧拉图 A B C D 1、哥尼斯堡七桥问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2、欧拉图(Euler) （2）定理4.1.1 无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。 （1）定义4.1.1 如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路。如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路，具有欧拉回路的图称为欧拉图。 先分析无向图： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 上述定理与推论可作为欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)＝5，deg(B)＝deg(C)＝deg(D)=3，故欧拉回路必不存在。 （3）推论 无向图G具有一条欧拉回路，当且仅当G连通且所有结点度数皆为偶数。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. （4）一笔画问题 要判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件予以解决。 见137页图4.1.3 (b)为欧拉路，有从左下结点到右下结点的一笔画。 (a)为欧拉回路，可以从任一结点出发，