运筹学05 3CPP.ppt

文档介绍：2017/11/11
1
运筹学 Operations Research
§ 中国邮递员问题
CPP
2017/11/11
2
运筹学 Operations Research
欧拉迹(Euler trail),欧拉环游(Euler tour),
欧拉图(Euler graph),半欧拉图(semiEuler graph),
非欧拉图(nonEuler graph).
2017/11/11
3
运筹学 Operations Research
证:(1)……; (2)…….
▌
几个结论:
(3)非平凡树必不是欧拉图.
(4)树可否为半欧拉图?
证明:……▌
2017/11/11
4
运筹学 Operations Research
“一笔画”问题
欧拉图和半欧拉图可一笔画;非欧拉图不可一笔画.
2017/11/11
5
运筹学 Operations Research
总统头像一笔画:
2017/11/11
6
运筹学 Operations Research
哥尼斯堡( Königsberg )七桥问题
1736年,瑞士,欧拉(Euler)
2017/11/11
7
运筹学 Operations Research
中国邮递员问题(Chinese Postman Problem,CPP)
一个邮递员投递信件必须走遍某街区的所有街道,,才能使得所走路线最短?
这一问题由我国数学家、山东师范大学数学系原教授管梅谷(Kuan Mei Ko)先生于1962年首先提出,并给出了一个算法(奇偶点图上作业法),故在国际上被称为中国邮递员问题.
图论模型:
以街道为边,以街口(街道与街道的交叉处)为顶点,以街道的长度为边的权作图G.
2017/11/11
8
运筹学 Operations Research
奇偶点图上作业法:1962年,Kuan M-K
基本思想:
若G是欧拉图,,此欧拉环游即为唯一最优投递路线;
若G不是欧拉图(包括半欧拉图和非欧拉图),则G不含有欧拉环游,故可行投递路线中必含有某些重复边,,应设法使这些重复边的权之和最短.
在算法上,奇偶点图上作业法要求从某一个可行投递路线开始,不断修正之,直到满足最优性判断标准,即得最优投递路线.
2017/11/11
9
运筹学 Operations Research
初始可行投递路线的确定:
找出图(半欧拉图和非欧拉图)G的所有奇度顶点,将其一一配对.
找出每一对奇度顶点之间的任一条路,将路上各边重复一次,(已变为欧拉图)中唯一的一条欧拉环游作为初始可行投递路线.
2017/11/11
10
运筹学 Operations Research
最优投递路线的判断标准:
(1)图的每条边至多有一条重复边;
若某条边的重复边的条数≥2,则可从中去掉偶数条,,并不改变顶点的奇偶性,即新图仍是欧拉图,且重复边的权之和变小,即新投递路线更优.