欧拉回路与中国邮递员问题_第1页
欧拉回路与中国邮递员问题_第2页
欧拉回路与中国邮递员问题_第3页
欧拉回路与中国邮递员问题_第4页
欧拉回路与中国邮递员问题_第5页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、13欧拉回路与中国邮递员问题、欧拉回路所谓欧拉回路与哥尼斯堡7桥问题相联系的.在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点与此相反，设G(V，E)为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G为欧拉图.在一个图中，连接一个节点的边数称为该节点的度数对欧拉图，我们有下列结果：定理1对连通图G(V,E),下列条件是相互等价的：(1)G是一个欧拉图；(2)G的每一个节点的度数都是偶数；(3)G的边集合E可以分解为若干个回路的并.证明：(1)= (2)已知G为欧拉图，则必存在一个欧拉回路回路中的节点

2、都是偶度数.(2)= (3)设G中每一个节点的度数均为偶数若能找到一个回路Ci使G=Ci，则结论成立否则，令Gi=GCi,由Ci上每个节点的度数均为偶数，则Gi中的每个节点的度数亦均为偶数于是在Gi必存在另一个回路C2.令G2=GiC2, -由于G为有限图，上述过程经过有限步，最后必得一个回路Cr使Gr=Gr-iCr上各节点的度数均为零，即Cr=Gr-i这样就得到G的一个分解GMC, C2L.wLCr(3)= (1)设G =C,C2Cr，其中Ci(l=i,2,r)均为回路由于G为连通图，对任意回路Ci,必存在另一个回路Cj与之相连，即G与Cj存在共同的节点.现在我们从图G的任意节点出发，沿着所

3、在的回路走，每走到一个共同的节点处，就转向另一个回路，这样一直走下去就可走遍G的每条边且只走过一次，最后回到原出发节点，即G为一个欧拉图.利用定理i去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了.下面介绍一种求欧拉回路的算法.二、弗罗莱算法算法步骤如下：(1)任取起始点V0,V0-；R;(2)设路R =0 他,当)，92“街2),;er(vViJ已选出，则从us ；ej中选出边计，使1与相连，除非没有其它选择，Gre+仍应为连通的.(3)重复步骤(2),直至不能进行下去为止.定理2连通的有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数(进数)与离开该点 的边数(出数)相等14下面给出此算法的matlab程序：function myeuler%求出一个图的欧拉回路n=input(输入起点)result=n;a=load(D:data.txt);%边权矩阵while length(result)=length(find(aO &a 0& a0 &a(k,:)0 &a(:, k)0&a0&a99999999);if length(p)=018sprin

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论