7-4欧拉图和汉密尔顿图

《7-4欧拉图和汉密尔顿图》由会员分享，可在线阅读，更多相关《7-4欧拉图和汉密尔顿图（49页珍藏版）》请在金锄头文库上搜索。

1、离散数学 Discrete Mathematics 第七章 图论第4讲 7-4 欧拉图和汉密尔顿图7-4 欧拉图和汉密尔顿图要求：1、理解欧拉图、汉密尔顿图的定义。2、掌握欧拉图的判定方法。3、会判断一些图不是汉密尔顿图。4、熟悉一些欧拉图和汉密尔顿图。学习本节要熟悉如下术语（9个）：欧拉路、欧拉图、欧拉回路、掌握6个定理，1个推论。单向欧拉路、单向欧拉回路、 汉密尔顿路、 汉密尔顿回路、汉密尔顿图、图的闭包一、欧拉图ABCD1、哥尼斯堡七桥问题七桥问题等价于在图中求一条回路，此回路 经过每条边一次且仅有一次。欧拉在1736年的论 文中提出了一条简单的准则，确定了哥尼斯堡七 桥问题是不能解的。

2、2、欧拉图(Euler)（2）定理7-4.1 无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。（1）定义7-4.1 如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路欧拉路（Euler walk）。如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路欧拉回路，具有欧拉回路的图称为，具有欧拉回路的图称为欧拉图欧拉图（Euler graph）。先分析无向图： 证明思路：1) 先证必要性:G有欧拉路 G连通连通 且（且（有有0 0个个 或或 2 2个奇数度结点个奇数度结点）设设G的欧拉路是点边序列v0e1v1e2 ekvk，其

3、中结点 可能重复，但边不重复。因欧拉路经过（所有边） 所有结点，所以图G是连通的。对于任一非端点结点对于任一非端点结点vi，在欧拉路中每当在欧拉路中每当vi出现一出现一 次，必关联两条边，故次，必关联两条边，故vi虽可重复出现，但是虽可重复出现，但是degdeg( (vi) )必必 是偶数。对于端点是偶数。对于端点, ,若若v0=vk ，则，则degdeg( (v0) )必是偶数，即必是偶数，即G 中无奇数度结点中无奇数度结点 。若。若v0vk ，则，则degdeg( (v0) )必是奇数，必是奇数， degdeg( (vk) )必是奇数必是奇数, ,即即G中有两个奇数度结点中有两个奇数度结点

4、 。必要性证毕。 2)再证充分性:(证明过程给出了一种构造方法)G连通连通且（且（有有0 0个个 或或 2 2个奇数度结点个奇数度结点） G有欧拉路 (1)(1)若有若有 2 2个奇数度结点个奇数度结点, ,则从其中一个结点开始构造一条迹则从其中一个结点开始构造一条迹, , 即从即从v0出发经关联边出发经关联边e1进入进入v1, ,若若degdeg( (v1) )为偶数为偶数, ,则必可由则必可由v1再经再经 关联边关联边e2进入进入v2, ,如此下去如此下去, ,每边仅取一次每边仅取一次, ,由于由于G是连通的是连通的, ,故必可故必可 到达另一奇数度结点停下到达另一奇数度结点停下, ,得到

5、一条迹得到一条迹L L1 1: :v0e1v1e2 ekvk。若。若G中中没有奇数度结点没有奇数度结点, ,则从任一结点则从任一结点v0出发出发, ,用上述方法必可回到结点用上述方法必可回到结点 v0, ,得到一条闭迹。得到一条闭迹。(2) (2) 若若L L1 1通过了通过了G的所有边的所有边, , L L1 1就是一条欧拉路。就是一条欧拉路。(3) (3) 若若G中去掉中去掉L L1 1后得到子图后得到子图G, ,则则G中每个结点度数都为中每个结点度数都为 偶数偶数, ,因为原来的图因为原来的图G是连通的是连通的, ,故故L L1 1与与G至少有一个结点至少有一个结点vi重合重合, , 在

6、在G中由中由vi出发重复出发重复(1)(1)的方法的方法, ,得到闭迹得到闭迹L L2 2。(4)(4)当当L L1 1与与L L2 2组合组合, ,若恰是若恰是G, ,得欧拉路得欧拉路, ,否则重复否则重复(3)(3), ,可得闭迹可得闭迹L L3 3, ,依此类推可得一条欧拉路。依此类推可得一条欧拉路。充分性证毕 上述定理与推论可作为欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)5，deg(B)deg(C)deg(D)=3，故欧拉回路必不存在。（3）定理7-4.1的推论 无向图G具有一条欧拉回路，当且仅当G连通且所有结点度数皆为偶数。

7、（4）一笔画问题要判定一个图G是否可一笔画出，有两种情况： 一是从图G中某一结点出发，经过图G的每一边一次 仅一次到达另一结点。另一种就是从G的某个结点出 发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件 予以解决。见303页图7- 4.3 (a)为欧拉路，有从v2到v3的一笔画。 (b)为欧拉回路，可以从任一结点出发，一笔画回到原出发点。练习: 311页（1）(1) 判定下图中的图形是否能一笔画。解： 完全图Kn每个结点的度数为n-1，要使n-1为偶数，必须n为奇数。故当n为奇数时，完全图Kn有欧拉回路。练习311页(3)(3) 确定n取怎样的值，完

8、全图Kn有一 条欧拉回路。（5）定义7-4.2 给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。可以将欧拉路和欧拉回路的概念推广到有向图中。（6）定理7-4.2 有向图G为具有一条单向欧拉回路，当且仅当G连通，并且每个结点的入度等于出度。有向图G有单向欧拉路，当且仅当G连通，并且恰有两个结点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多1。证明思路与定理7-4.1类似应用：街道清扫车问题小区大门21例1 有向欧拉图应用示例：计算机鼓轮的设计。鼓轮表面分成24=16等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信

9、号1，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息4个触点a,b,c,d读出1101(状态图中的边e13),转一角度后将读出1010 (边e10)。问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。01111 111100 000001110abcd设有一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数000，001，111，设ai0,1，从结点a1 a2 a3可引出两条有向边，其终点分别是a2 a30以及a2 a31。该两条边分别记为a1 a2 a30和a1 a2 a31。按照上述方法，对于八

10、个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1 a2 a3a4和a2 a3a4a5的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。010101110100011001111000e10=1010e13=1101e5=0101e3=0011e11=1011e6=0110e7=0111e14=1110e15=1111e12=1100e2=0010e4=0100e1=0001e8=1000e9=1001e0=0000a1 a2 a3 (=000)

11、 0a1 a2 a3 (=000) 1a1 a2 a3 (=001) 1a1 a2 a3 (=100) 0a1 a2 a3 (=111) 0a1 a2 a3 (=111) 1a1 a2 a3 (=110) 0 a1 a2 a3 (=011) 1所求的欧拉回路为：e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8(e0) （从图示位置开始）e13e10e5e11e7e15e14e12e8e0e1e2e4e9e3e6 (e13) 所求的二进制序列为：0000100110101111 (0) 1101011110000100 (1) （从图示位置开始）上述结论可推广到鼓轮具

12、有n个触点的情况。构造2n-1 个结点的有向图，每个结点标记为n-1位二进制数,从结点 a1a2a3.an-1出发,有一条终点为a2a3.an-10的边,该边记为 a1a2a3.an-10；还有一条终点标记为a2a3.an-11的边,该边记 为a1a2a3.an-11 。邻接边的标记规则为：“第一条边后n-1 位与第二条边前n-1位二进制数相同”。二、汉密尔顿图（Hamilton）几个问题 在一个大城市，有很多取款机，那么，如何制定出一个最优的路 线，使运钞车过每个提款机一次就能运送完钱钞？货郎担问题旅行商人问题(TSP) 考虑在七天内安排七门课程的考试，要求同一位教师所任教的两 门课程考试不

13、安排在接连的两天里，如果教师所担任的课程都不多 于四门，则是否存在满足上述要求的考试安排方案？时间表问题 国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一 格仅一次并最后回到出发的棋盘格子？ 在一个至少有5人出席的圆桌会议上（会议需要举行多次），为 达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与 前次不同，这是否可行？请应用图论知识进行论证。 周游世界问题与欧拉回路类似的是汉密尔顿回路。它是1859年汉密尔 顿首先提出的一个关于12面体的数学游戏：能否在图7-4.6中 找到一个回路，使它含有图中所有结点一次且仅一次？若把 每个结点看成一座城市，连接两个结点的边看成是交通线，

14、 那么这个问题就变成能否找到一条旅行路线，使得沿着该旅 行路线经过每座城市恰好一次，再回到原来的出发地？他把 这个问题称为周游世界问题。周游世界问题汉密尔顿图范更华：歪打正着学了图论 灵光一闪发现定理科学中国人（2005）年度人物汉密尔顿回路问题是图论最古老的研究课题之一，是至今未解决的世界 难题，在许多领域有着重要应用。经过多年艰苦攻克，范更华的这一项 目在这一问题的研究上开辟 了一条新的途径，证明若图中每对距离为2 的点中有一点的度数至少是图的点数的一半，则该图存在哈密尔顿回路 。了此成果引发了大量后续工作，以“范定理”、“范 条件”、“范类 型”被广泛引用而出现于多种国际权威学术刊物，并

15、作为定理出现在国 外的教科书中。 新华网 2006.1.10（1）定义7-4.3 给定图G，若存在一条路经过 图中的每个结点恰好一次，这条路称作汉密尔顿汉密尔顿 路路。若存在一条回路，经过图中的每个结点恰好 一次，这条回路称作汉密尔顿回路汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图汉密尔顿图。2、汉密尔顿图图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图（2）定理7-4.3 若图G具有汉密尔顿 回路，则对于结点集V的每个非空子集S均有W(G- S)|S|，其中W(G-S)是G-S的连通分支数。证明 设C是G的一条汉密尔顿回路，对于V的任何一个 非空子集S，在C中删去S中任一结点a1，则C-

16、a1是连通的 非回路， W(C- a1)=1， |S|1，这时 W(C-S)|S|。 若 再删去S中另一结点a2，则W(C-a1-a2)2，而 |S|2，这 时 W(C-S)|S|。由归纳法可得：W(C-S)|S|。同时C-S 是G-S的一个生成子图，因而W(G-S)W(C-S)，所以W(G- S)|S|。 C经过图G的每个结点恰好一次 ， C与G的结点集合是同一个， 因此 C-S与G-S的结点集合是同 一个。 此定理是必要条件，可以用来证明一个图不是汉密尔顿图。如右图，取S=v1,v4 ，则G-S有3个连通分支，不满足W(G-S)|S|，故 该图不是汉密尔顿图。说明：此定理是必要条件而不是充分条件。有的图满足此必要条件，但也是非汉密尔顿图。彼得森(Petersen)图例