您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
离散数学 第2版 教学课件 作者 王元元 离散第19讲 欧拉图与哈密顿图.ppt38页
本文档一共被下载：
次 ,本文档已强制全文免费阅读，若需下载请自行甄别文档质量。
文档加载中...广告还剩秒
需要金币：100 &&
你可能关注的文档：
··········
··········
第19讲 欧拉图与哈密顿图 欧拉图与哈密顿图 回顾 顶点的度数 握手定理：∑d v
2m 拟路径、路径、闭路径 通路、回路 定理8-4：有拟路径则有通路 定理8-5：有闭路径则有回路 连通 无向图G连通 有向图G连通 强连通、单向连通、弱连通 欧拉图与欧拉路径 定义： 图G称为欧拉图 Euler graph ，如果图G上有一条经过G的所有顶点、所有边的闭路径。 图G称为欧拉路径 Euler walk ，如果图G上有一条经过G所有顶点、所有边的路径。
例 哈密顿图与哈密顿通路 定义： 无向图G称为哈密顿图 Hamilton graph ，如果G上有一条经过所有顶点的回路 也称这一回路为哈密顿回路 。 无向图G称有哈密顿通路 非哈密顿图 ，如果G上有一条经过所有顶点的通路 非回路 。 例 欧拉图与哈密顿图判断 （a）既为欧拉图又为哈密顿图； （b）是欧拉图而非哈密顿图； （c）是哈密顿图却非欧拉图； （d）既非欧拉图也非哈密顿图 欧拉路径与哈密顿通路 （a）既有欧拉路径又有哈密顿通路； （b）有欧拉路径而无哈密顿通路； （c）有哈密顿通路却无欧拉路径； （d）既无欧拉路径也无哈密顿通路。 欧拉图的性质 G为一欧拉图 G显然是连通的 各顶点的度均为偶数 由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。
欧拉图的充要条件 定理8.11 有限无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。
证明 对G的边数归纳。 当m
1时，G必定为单顶点的环，显然为欧拉图。 定理8.11充分性证明 设边数少于m时成立，现考虑有m条边的图G。 从G的任一顶点v0出发经关联边e1“进入”v1，若deg v1 为偶数，则必可由v1再经关联边e2进入v2，如此进行下去，每边
正在加载中，请稍后...哈密顿回路最邻近算法的改进
1.最邻近算法 问题的数学模型:G为一完全图,有n个结点v:,v:,……,认,,其中任意两个边尸都赋于一个权叽=w(v;,vj),所有的权可以组成一个矩阵W=(叭)。 最邻近算法 l.lw=(叭)中找出最小的w。二w(。,,马),若有。个(至少应有两个)。不妨任选一个,另州1尸(l)=v,,走二l。 1.2令,,,=月v(走),在w的第,,,行(二,,,,,,w。,:,……...&
(本文共2页)
权威出处：
一、分析 (一)哈密顿回路:指一个图中,从图的一个顶点出发, 沿着图中的边(各顶点连线),经过所有顶点各一次,最终 又回到起点,这条回路就称为哈密顿回路。 (二)最短哈密顿回路:在一个有向网中,哈密顿回路 可能有多条,分别计算出每条哈密顿回路中每条边上的 权值之和,找出最小的,这条权值之和最小的哈密顿回路, 就是最短哈密顿回路。 二、算法 (一)列出有向网中所有的边,并按权值由小到大排 序。 (二)取前n条边,判断它是否构成哈密顿回路。(条 件:1.n个顶点全出现;2.顶点出现的次数等于2并且每 一个顶点在弧头和弧尾各出现一次;3.不存在小于n个顶 点的回路即小回路。) (三)满足以上条件,则这前n条边构成的路就是最短 哈密顿回路;否则,将剩下的边由小到大来替换,每替换一 次就检查一次条件1 .2.3.,如满足,结束;否则,继续,直 到所有的路径全搜索结束。 三、描述 (一)用邻接矩阵存放有向网; (二)用队列存放结点; (三)...&
(本文共2页)
权威出处：
1　问题的提出1)任给一个无向图 ,如何求无向图的哈密顿图的回路 ,首先必须判断该图是否是哈密顿图 ,即是否有一条经过所有顶点的回路。如果图很复杂又有哈密顿图回路 ,用手工是很难找到的 ,该算法是 :根据图的结点数先求其完全图的所有哈密顿回路 ,在所有哈密顿回路中去掉那些在实际图中有不存在边的哈密顿回路 ,最后得到任意图的所有哈密顿回路 ,如果全部去掉 ,则该图不是哈密顿图。从而可以证明一个任意图是否是哈密顿图。2 )在求解“旅行商问题”时 ,考虑的是带权完全无向图 ,“分支定界法”只是求出最小的哈密顿回路 ,对于任意图是不可行的。3 )在求解“旅行商问题”时 ,有时只求出路径最小的哈密顿回路不一定是最佳的哈密顿回路。因为在旅行时 ,所考虑的不仅仅是费用或旅程 ,比如 ,有的路线虽短 ,但路线人员拥挤 ,如果单纯按最小的哈密顿回路旅行是不现实的 ,反而费用更高。此时求出若干最小的哈密顿回路 ,甚至求出所有的哈密顿回路 ,才能正确...&
(本文共3页)
权威出处：
任给一个无向图,如何求无向图的哈密顿图的回路,有许多经典算法,如,“贪心算法”,“分忮定界法”,“回溯算法”等[1].本文提出一种新的思路,对经典问题“求哈密顿图回路”,使用现代的“遗传”思想[2],设计了一种算法.算法的基本思想是:首先,根据图的结点数使用“继承”算法先求其完全图的所有哈密顿回路,然后使用“选择”算法在所有哈密顿回路中去掉那些在实际图中有不存在边的哈密顿回路,最后得到任意图的所有哈密顿回路,如果全部去掉,则该图不是哈密顿图.从而可以证明一个任意图是否是哈密顿图.本文约定,H代表哈密顿,n代表图的结点数,m代表图的边数.1　算法的依据定理1　简单图G中任何不同的H回路至少有两条不同的边.证明　令H1是图G的一个H回路.任意H回路子图的结点的度数为2.在H1中任取一个边(vi,vj),删去后,再加上任何其它一个边,必然使vi或vj的度数为1.此时,该子图不是回路,更不是H回路.故,任何不同的H回路至少有两条不同的边...&
(本文共3页)
权威出处：
一、引言 判断一个图是否有Hamilton回路的充要条件一直没有解决,尽管充分条件与必要条件都有了,而且人们对图的研究已经非常深入—一个例子是竞赛图的研究[’]。在这里我们通过对求无向完全图的哈密顿回路总数的探讨,引申Hamilton回路的求法,另一个引申就是NP完全问题的解法。当然,这里引申出来的方法仍然是完全搜索式的,但在下面对完全图的Hamil-ton回路的分析中可以看到,里面没有重复的情况。比如两个黑盒子中一个装了一个球,你只能一个个试,才能找到那个球。同样,在求解Ham让ton回路中不能确定在哪种情况,必然有或没有Hamilton回路的时候(很多情况下的确如此),只好一个一个地找,找的时候只要不重复,就是好方法。二、基本概念 图:由点与边构成的集合,其中相关系的两点构成一条边。形式化的定义为:图G一(V,E)是一个系统,其中V是非空有限集合,V中的元素称为结点;E是有限的集合,E中的元素称为边,且E中的元素与V中的一对...&
(本文共3页)
权威出处：
近10年内，计算机科学理论主要集中在各种算法的研究和设计上，特别是计算机网络的普及应用，网络图论已成为计算机科学工作者进行算法研究与设计的一个有用的分析工具．图论算法和算法图论［'冲的一些典型问题的解决，引起了人们的极大兴趣．做为网络数据结构的数学模型--图结构的使用，经常要求在较短时间内输出简单图的全部可能回路，找出其中最短的哈密顿回路．本文给出的算法是通过集合矩阵连接相乘，逐步构造通路矩阵序列的方法，直接输出图的全部最短哈密顿回路或输出"非哈密顿图"的信息．1墓本概念定义1．1由1，2，...，n（n＜9）中的无重复数字组成的长度小于等于n＋l的数字串构成的集合（仅当长度为n＋l时首尾数字可相同），称为L集合．定义1．2设M一｛m；i-l，...，r｝，N一｛n。Ij-1，...，s｝分别为由r个数字串和占个数字串构成的L集合，则M和N的连接积P仍然是一个L集合，其元素为将N中数字字符并接到M中数字串后面形成的长度小于等于n...&
(本文共4页)
权威出处：
扩展阅读：
CNKI手机学问
有学问，才够权威！
出版：《中国学术期刊（光盘版）》电子杂志社有限公司
地址：北京清华大学 84-48信箱 大众知识服务
互联网出版许可证 新出网证(京)字008号
京ICP证040431号
服务咨询：400-810--9993
订购咨询：400-819-9993
传真：010-君，已阅读到文档的结尾了呢~~
无向完全图的哈密顿回路
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
无向完全图的哈密顿回路
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口哈密顿回路充要判别法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
哈密顿回路充要判别法
上传于|0|0|文档简介
&&用矩阵的方法介绍了哈密顿回路的判别方法
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩2页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
哈密顿回路数无向完全图Kn(n>=3)中共有多少条不同的哈密顿回路?K3,K4,K5中各有多少条不同的哈密顿回路(n,3,4,5均为脚标)
扫二维码下载作业帮
2亿+学生的选择
设Kn的每一条哈密顿回路是v1,v2...vn,v1v1,v2...vn对应完全图顶点的一个全排列所以Kn中不同的哈密顿回路有N!条K3是3!=6K4是4!=24K5是5!=120
为您推荐：
其他类似问题
扫描下载二维码}