第十五章欧拉图与哈密顿图s.ppt
《第十五章欧拉图与哈密顿图s.ppt》由会员分享,可在线阅读,更多相关《第十五章欧拉图与哈密顿图s.ppt(40页珍藏版)》请在三一文库上搜索。
1、第十五章 欧拉图与哈密顿图,15.1 欧拉图,1736年数学家欧拉发表了第一篇图论论文,解诀了哥尼斯堡七桥问题。,定义(欧拉通路和欧拉回路) 通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路 通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路 定义(欧拉图和半欧拉图) 具有欧拉回路的图称为欧拉图 具有欧拉通路无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图,(1)欧拉图。 (2)半欧拉图。 (3)不存在欧拉通路,也不存在欧拉回路。 (4)欧拉图。 (5)不存在欧拉通路,也不存在欧拉回路。 (6)不存在欧拉通路,也不存在欧拉回路。,例,(1) (2) (3),
2、(4) (5) (6),无向欧拉图与无向半欧拉图的判断方法 定理15.1(无向欧拉图的判定)无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。 定理15.2(无向半欧拉图的判定)无向图G是半欧拉图当且仅当G是连通图,且G中恰有两个奇度顶点。,(1) (2) (3),判断所示两图是否为欧拉图、半欧拉图?,有向欧拉图与有向半欧拉图的判断方法 定理15.3 (有向欧拉图的判定)有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。 定理15.4(有向半欧拉图的判定)有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其
3、余顶点的入度都等于出度。,(4) (5) (6),由两判定定理,立即可知 (4)为欧拉图, (5)、(6)即不是欧拉图,也不是半欧拉图。,欧拉图的性质:欧拉图可以分解成若干个边不重的圈。,定理15.5(欧拉图的判定) G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。,中国的“一笔画”的问题 从图某一点出发,线可以相交但不能重合将图画完的问题。 可以看出在“一笔画”的问题中,终点与始点重合的图对应着欧拉图,不重合的对应半欧拉图。,例15.2(P296),v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2,Fleury算法 (1)任取v0V(G),令P0=v0。 (2)
4、设Pi=v0e1v1e2eivi已经行遍,则按下面方法来从E(G)-e1,e2,.,ei中选取ei+1: (a)ei+1与vi相关联; (b)除非无别的边可供选择,否则ei+1不应该为 G-e1,e2,.,ei中的桥。 (3)当(2)不能再进行时,算法停止,得到的Pn=v0e1v1e2envn为G中的一条欧拉回路。,桥:设eE(G),若p(G-e)p(G), 则称e为G中的桥。,例15.2(P296),v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2,例15.2(P296),利用欧拉图可以解决哥尼斯堡七桥问题:从某地出发,对每座跨河桥只走一次,而在遍历了七座桥之后,却又能回到原
5、地。,由定理15.1(无向欧拉图的判定定理)可知该问题无解。,思考 如下图所示,从一房间出发,问能否不重复地穿过每一道门,通过所有房间?,15.2 哈密顿图,1859年,爱尔兰数学家威廉哈密尔顿发明了一个旅游世界的游戏。将一个正十二面体的20个顶点分别标上世界上大城市的名字,要求玩游戏的人从某城市出发沿12面体的棱,通过每个城市恰一次,最后回到出发的那个城市。,哈密尔顿游戏是在左图中如何找出一个包含全部顶点的圈。,定义(哈密顿通路和哈密顿回路) 经过图(有向图或无向图)每个顶点一次且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路(初级回路)称为哈密顿回路。 定义(哈密顿图和半哈
6、密顿图) 存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图称为半哈密顿图。 平凡图是哈密顿图。,(1)(2)(3)(4)为哈密顿图 (5)为半哈密顿图 (6)既不是哈密顿图,又不是半哈密顿图。,(1) (2) (3),(4) (5) (6),到目前为止,还没有找到判断哈密顿图简单的充分必要条件。 下面介绍哈密顿图和半哈密顿图的必要条件 定理15.6 设无向图G=是哈密顿图,V1是V的任意非空子集,则有p(G-V1)|V1|,其中p(G-V1)为G-V1的连通分支数。 推论 设无向图G=是半哈密顿图,V1是V的任意非空子集,则有p(G-V1)|V1|+1。 注意: (1)定
7、理15.6和推论是必要条件。 (2)两定理可以证明一个图不是哈密尔顿图或半哈密顿图。,易见p(G-v1,v2)=3,|v1,v2|=2 p(G-v1,v2)|v1,v2| 不满足定理15.6,所以图G不是哈密顿图。,例如,G,G-v1,v2,彼得松图,彼得松图满足定理15.6,但不是哈密顿图。,例如,下面给出哈密顿图和半哈密顿图的充分条件 定理15.7 设G=为n阶无向简单图,如G中任意两个不相邻的顶点vi,vj,均有d(vi)+d(vj)n-1,则G中存在哈密顿通路,即G为半哈密顿图。 推论 设G=为n(n3)阶无向简单图,如G中任意两个不相邻的顶点vi,vj,均有d(vi)+d(vj)n,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十五 章欧拉图 哈密
链接地址:https://www.31doc.com/p-2572931.html