欧拉图与汉密尔顿图.ppt

《欧拉图与汉密尔顿图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、欧拉图与汉密尔顿图主要内容欧拉图欧拉图的判定汉密尔顿图汉密尔顿图的必要条件汉密尔顿图的充分条件学习要点与基本要求实例分析问题的提出哥尼斯堡七桥问题欧拉图及相关概念定义7-4.1给定无孤立结点图G，欧拉路：经过图中每边一次而且仅一次的一条路。欧拉回路：经过图中每边一次而且仅一次的一条回路.欧拉图：含有欧拉回路的图。半欧拉图：含有欧拉路的图。几点说明：(1)上述定义对无向图和有向图都适用.(2)规定平凡图为欧拉图.(3)欧拉路是迹,欧拉回路是封闭的迹.(4)环不影响图的欧拉性.举例下列图中，哪些是欧拉图？哪些是半欧拉图？在非（

2、半）欧拉图中至少增加几条边才能成为欧拉图？欧拉图半欧拉图非（半）欧拉图欧拉图半欧拉图非（半）欧拉图欧拉图的判别定理7-4.1无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。证明必要性。设G具有欧拉路P=v0e1v1e2v2…eiviei+1…ekvk，其中结点可能重复出现，但边不重复且包括了G中的所有边。因此P经过图G中的所有结点，所以G是连通的。对任意非端点的结点vi，在欧拉路中每当vi出现一次，必然关联两条边，vi所关联的所有边必然都出现在欧拉路中一次而且仅一次，所以deg(vi)为偶数。定理7-

3、4.1的证明对于端点，若v0=vk，则d(v0)为偶数，即G中奇数度结点数为零，这时G是欧拉图。若v0≠vk，则d(v0)为奇数，d(vk)为奇数，因此G中就有两个奇数度结点，这时G是半欧拉图。充分性。若图G连通，有零个或两个奇数度结点，用如下方法构造一条欧拉路：(1)若有两个奇数度结点，则从其中一个结点开始构造一条迹，即从v0出发经关联边e1进入v1，若deg(v1)为偶数，则必可由v1经关联边e2进入v2，依此类推，每边仅取一次。定理7-4.1的证明由于G是连通的，故必可到达另一个奇数度结点停止，得到一条迹L1：v0e

4、1v1e2v2…eiviei+1…ekvk。若G中没有奇数度结点，则从任意结点v0出发，用上述方法必可回到v0，得到一条闭迹L1。(2)若L1经过G的所有边，则L1就是欧拉路。(3)否则，在G中删掉L1中的边，得到G’，则G’中每个结点的度必为偶数。这是因为：如果L1是不封闭的，则对每个非端点vi，L1包含了与vi关联的所有边中的偶数条，即deg’(vi)=deg(vi)-L1中与vi关联的边数，因为deg(vi)为偶数，所以deg’(vi)为偶数，而deg’(v0)=deg(v0)-1为偶数，定理7-4.1的证明deg’

5、(vk)=deg(vk)-1为偶数.如果L1是封闭的，同样G’中每个结点的度为偶数。因为G是连通的，所以L1与G’至少有一个结点vj是重合的，则按照上面的方法可以在G’中从vj出发构造一条闭迹L2。(4)若L1与L2组合在一起恰好包含了G中的所有边，则得到欧拉路。否则重复(3)得到闭迹L3，依次类推直到得到一条欧拉路。欧拉路的演示定理7-4.1的推论推论无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。思考题：无向连通图含G有m个奇数度结点，问（1）至少加入多少条边才能使图G变为欧拉图？（2）至少加入

6、多少条边才能使图G变为半欧拉图？欧拉图的应用：一笔画问题七桥问题的解：没有满足要求的路线。一笔画问题的判别：图可一笔画有两种情况：(1)从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。——欧拉路(2)从图G中某一结点出发，经过图G的每一边一次仅一次再回到该结点。——欧拉回路实例例下图可以一笔画吗？请找出一种画法。有向图中的欧拉路与欧拉回路定义7-4.2给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。定理7-4.2有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点

7、入度等于出度。一个有向图G具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大，另一个结点的入度比出度小1。应用举例例1计算机鼓轮的设计。导体，1绝缘体，0设有旋转鼓轮其表面被分成24个部分，如左图所示。其中每部分分别用绝缘体或导体组成，其输出信号分别为0和1。有4个触点，鼓轮每旋转1个部分，触点输出一个4位二进制数，如图所示的位置输出：1101问鼓轮上16个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制信息。设一个8结

8、点的有向图，其结点分别记为3位二进制数{000,001,010,011,100,101,110,111}，设ai∈{0,1}，从结点a1a2a3可引出两条边，其终点分别是a2a30和a2a31。按照这种方法，该有向图共有16条边，从结点a1a2a3到结点a2a3a4的有向边标记为a1a2a3a4，而结点