欢迎来到天天文库
浏览记录
ID：58411068
大小：449.50 KB
页数：9页
时间：2020-09-07
《教学课件第六节中国邮递员问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六节中国邮递员问题所谓中国邮递员问题，用图的语言来描述，就是给定一个赋权连通图G，要寻求一个圈，使得经过G的每条边至少一次，并且圈的总圈数最小。这个问题是由我国数学家管梅谷教授于1962年首先提出来的，因此称为“中国邮路问题”．这个问题和所谓的“一笔画问题”联系密切。欧拉链是连通无向图的一条链，链中每条边恰出现一次．欧拉图含有一条闭的欧拉链的图．图8-278.6.1一笔画问题定理8.5①当且仅当连通图G的全部顶点都是偶次顶点时，图G才是欧拉图；②当连通图G恰有两个奇次顶点时，G才有欧拉链．图8-28（必须从其中一
2、个奇次顶点出发到达另一个奇次顶点）一个邮递员从邮局出发，将邮件投递到他管辖的所有街道，最后回到邮局，如何安排他的行驶路线，使总路程最短．其实质就是在赋权连通图中求一个每条边都至少通过一次的闭链，使总权数最小．8.6.2邮路问题图8-28解决中国邮路问题的方法：用加边法将原图变为欧拉图定理8.6加边法化欧拉图的原则和方法是：①在赋权图G的一些边上，加且仅加一条重复边，使图G的每个顶点成为偶次顶点；②赋权图G的每个闭链上，重复边权之和不超过该闭链总权数的一半或该闭链中非重复边权之和．例8.8设有图8-30（a）所示的赋
3、权图，构造总权数最小的闭的欧拉链．②赋权图G的每个闭链上，重复边权之和不超过该闭链总权数的一半或该闭链中非重复边权之和．设重复边权之和为a，非重复边权之和为b：作业195页习题88.3题
此文档下载收益归作者所有
