中国邮路问题_第1页
中国邮路问题_第2页
中国邮路问题_第3页
中国邮路问题_第4页
中国邮路问题_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

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

文档简介

2.3.3中国邮递员问题一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？

描述为图论语言：在连通加权无向图G中，寻找一条经过每边至少一次且权和最小的闭链，即G的最优环游。①如果对应的图G是欧拉图，那么对应于邮局的顶点出发的任何一条欧拉回路都是符合上述要求的投递员的最优投递路线。如果图G只有两个奇度数顶点x和y，则存在一条以x和y为端点的欧拉路。因此，所要求的最优投递路线是由这条欧拉路+边{x，y}。

由于图G有偶数个奇度数顶点，对于任两个奇度数顶点x和y，在G中必有一条路连接。将这条路上的每条边改为二重边得到的新图，则x和y就变为的偶度数顶点，在这条路上的其他顶点的度数均增加2，即奇偶性不变。于是的奇顶点个数比G的奇顶点个数少2，对重复上述过程得，再对重复上述过程得，……，经若干次后，可将G中所有奇度数顶点变为偶度数顶点，从而得到多重欧拉图G'。

②如果连通图不是欧拉图。这个欧拉图G'的一条欧拉回路就相应于中国邮递员问题的一个可行解，且欧拉回路的长度等于G的所有边的长度加上每次连奇度数顶点的路的长度。定理：设P是加权连通图G中一条包含G的所有边

至少一次的闭链，则P最优的充要条件是

（1）P中没有二重以上的边；

（2）在G的每条圈C中，重复边集E的长度之和不超过这个圈长度的一半。奇偶点图上作业法把中的所有奇度数顶点配成对，将每对奇度数顶点之间的路上的每边改为二重边，得到一个新图，新图中没有奇度数顶点，即为欧拉图。若中某一对顶点之间有多于2两条边连接，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点，直到每一对相邻顶点至多由2条边连接，得到图。检查的每一个圈C，若某一个圈上重复边的权和超过此圈权和的一半，则将C按定理1必要性的证明过程进行调整，重复这一过程，直到对的所有圈，其重复边的权和不超过此圈权和的一半，得到。用Fleury

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论