欧拉回路与中国邮递员问题

欧拉回路与中国邮递员问题一、欧拉回路所谓欧拉回路与哥尼斯堡7桥问题相联系的.在哥尼斯堡7桥问题中,欧拉证明了不存在这样的回路,使它经过图中每条边且只经过一次又回到起始点.与此相反,设G(V,E)为一个图,若存在一条回路,使它经过图中每条边且只经过一次又回到起始点,就称这种回路为欧拉回路,并称图G为欧拉图.在一个图中,连接一个节点的边数称为该节点的度数.对欧拉图,我们有下列结果:定理1对连通图G(V,E),下列条件是相互等价的:(1)G是一个欧拉图;(2)G的每一个节点的度数都是偶数;(3)G的边集合E可以分解为若干个回路的并.证明:已知G为欧拉图,则必存在一个欧拉回路.回路中的节点都是偶度数.设G中每一个节点的度数均为偶数.若能找到一个回路C1使G=C1,则结论成立.否则,令G1=G\C1,由C1上每个节点的度数均为偶数,则G1中的每个节点的度数亦均为偶数.于是在G1必存在另一个回路C2.令G2=G1\C2,···.由于G为有限图,上述过程经过有限步,最后必得一个回路Cr使Gr=Gr-1\Cr上各节点的度数均为零,即Cr=Gr-1.这样就得到G的一个分解.设,其中(I=1,2,…,r)均为回路.由于G为连通图,对任意回路,必存在另一个回路与之相连,即与存在共同的节点.现在我们从图G的任意节点出发,沿着所在的回路走,每走到一个共同的节点处,就转向另一个回路,···,这样一直走下去就可走遍G的每条边且只走过一次,最后回到原出发节点,即G为一个欧拉图.利用定理1去判断一个连通图是否为欧拉图比较容易,但要找出欧拉回路,当连通图比较复杂时就不太容易了.下面介绍一种求欧拉回路的算法.二、弗罗莱算法算法步骤如下:(1)任取起始点(2)设路已选出,则从E\中选出边,使与相连,除非没有其它选择,仍应为连通的.(3)重复步骤(2),直至不能进行下去为止.定理2连通的有向图存在欧拉回路的充分必要条件是对任意节点,进入该节点边数(进数)与离开该点的边数(出数)相等---本文来源于网络,仅供参考,勿照抄,如有侵权请联系删除---下面给出此算法的matlab程序:functionmyeuler%求出一个图的欧拉回路n=input('输入起点')result=;a=load('D:\data.txt');%边权矩阵whilelength(result)~=length(find(a>0a<99999999))n=result(length(result));temp=a(n,:);p=find(temp>0a<99999999);iflength(p)==0sprintf('不是euler图')breakendresult=[result,p(1)];a(n,p(1))=0;endresult三、中国邮递员问题一名邮递员带着要分发的邮件从邮局出发,经过要分发的每个街道,送完邮件后又返回邮局.如果他必须至少一次走过他管辖范围内的每一条街道,如何选择投递路线,使邮递员走尽可能少的路程.这个问题是由我国数学家管梅谷先生(山东师范大学数学系教授)在1962年首次提出的,因此在国际上称之为中国邮递员问题.用图论的述语,在一个连通的赋权图G(V,E)中,要寻找一条回路,使该回路包含G中的每条边至少一次,且该回路的权数和最小.也就是说要从包含G的每条边的回路中找一条权数和最小的回路.如果G是欧拉图,则很容易由弗罗莱算法求出一个欧拉回路,但是若G不是欧拉图,即存在奇度数的节点,则中国由递员问题的解决要困难得多.本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法.首先注意到,若图G有奇数度节点,则G的奇数度节点必是偶数个(握手定理).把奇数度节点分为若干对,每对节点之间在G中有相应的最短路,将这些最短路画在一起构成一个附加的边子集.令G/=G+E/,即把附加边子集E/叠加在原图G上形成一个多重图G/,这时G/中连接两个节点之间的边不止一条.显然G/是一个欧拉图,因而可以求出G/的欧拉回路.该欧拉回路不仅通过原图G中每条边,同时还通过E/中的每条边,且均仅一次.邮递员问题的难点在于当G的奇数度节点较多时,可能有很多种配对方法,应怎样选择配对,能使相应的附加边子集E/的权数ω(E/)为最小?为此有下列定理.定理3设G(V,E)为一个连通的赋权图,则使附加边子集E/的权数ω(E/)为最小的充分必要条件是G+E/中任意边至多重复一次,且G+E/中的任意回路中重复边的权数之和不大于该回路...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供参考,付费前请自行鉴别。
3、如文档内容存在侵犯商业秘密、侵犯著作权等,请点击“举报”。

常见问题具体如下:

1、问:已经付过费的文档可以多次下载吗?

      答:可以。登陆您已经付过费的账号,付过费的文档可以免费进行多次下载。

2、问:已经付过费的文档不知下载到什么地方去了?

     答:电脑端-浏览器下载列表里可以找到;手机端-文件管理或下载里可以找到。

            如以上两种方式都没有找到,请提供您的交易单号或截图及接收文档的邮箱等有效信息,发送到客服邮箱,客服经核实后,会将您已经付过费的文档即时发到您邮箱。

注:微信交易号是以“420000”开头的28位数字;

       支付宝交易号是以“2024XXXX”交易日期开头的28位数字。

客服邮箱:

biganzikefu@outlook.com

所有的文档都被视为“模板”,用于写作参考,下载前须认真查看,确认无误后再购买;

文档大部份都是可以预览的,笔杆子文库无法对文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;

文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为依据;

如果您还有什么不清楚的或需要我们协助,可以联系客服邮箱:

biganzikefu@outlook.com

常见问题具体如下:

1、问:已经付过费的文档可以多次下载吗?

      答:可以。登陆您已经付过费的账号,付过费的文档可以免费进行多次下载。

2、问:已经付过费的文档不知下载到什么地方去了?

     答:电脑端-浏览器下载列表里可以找到;手机端-文件管理或下载里可以找到。

            如以上两种方式都没有找到,请提供您的交易单号或截图及接收文档的邮箱等有效信息,发送到客服邮箱,客服经核实后,会将您已经付过费的文档即时发到您邮箱。

注:微信交易号是以“420000”开头的28位数字;

       支付宝交易号是以“2024XXXX”交易日期开头的28位数字。

笔杆子文秘
机构认证
内容提供者

为您提供优质文档,供您参考!

确认删除?