2009-7-26 1
运 筹 学 Operations Research
§ 6.3 中国邮递员问题（ CPP）
欧拉迹 （ Euler trail）,经过图的每条边恰好一次的迹；
欧拉环游 （ Euler tour）,闭的欧拉迹；
欧拉图 （ Euler graph）,含有欧拉环游的图；
半欧拉图 （ SemiEuler graph）,仅含有欧拉迹,不含有欧拉环游的图；
非欧拉图（ NonEuler graph）,otherwise,
2009-7-26 2
运 筹 学 Operations Research
2009-7-26 3
运 筹 学 Operations Research
.
)u le r1 7 3 6(1
恰含有两个奇顶点是半欧拉图不含有奇顶点；是欧拉图为非空连通图，则设，
GG
GG
GETh
证,（ 1）
（ 2）
▌
2009-7-26 4
运 筹 学 Operations Research
.)1(为欧拉图，则若图 G
几个结论：
.2)(21h
Vv
vdTG 有，由必为连通图，证,?
.,
);3()2(
,都为偶数为欧拉图为奇数为欧拉图
nmK
K
nm?
它们何时为半欧拉图？
(3)非平凡树 树必非欧拉图,
证,∵ 非平凡树均至少有两个 叶,▌
树可否为半欧拉图？
▌
2009-7-26 5
运 筹 学 Operations Research
,一笔画,问题,
能否一笔 （ 无重笔 ） 画出整个图？
对欧拉图,任选一个顶点为始点和终点,即可一笔画；
对半欧拉图,任选两个奇度顶点的一个为始点,另一个为终点,即可一笔画；
对非欧拉图，不可一笔画,
2009-7-26 6
运 筹 学 Operations Research
总统头像一笔画：
美国画家 Oscar Berger曾以其非凡的绘画技巧，独创一格地把,一笔画,原理运用到人物肖像画领域．在他的笔下，
从华盛顿到里根的前后 40位美国总统的脸部特征被刻画得惟妙惟肖，甚至喜怒哀乐的表情也都和盘托出了．下面是几幅中国读者比较熟悉的总统头像：
2009-7-26 7
运 筹 学 Operations Research
更令人吃惊的是，他竟是把一气呵成地一笔画出来的,Berger可谓开风气之先，在其作品示范与影响之下，绘画界居然刮起了一股不大不小的漫画名人之风．
2009-7-26 8
运 筹 学 Operations Research
哥尼斯堡（ Knigsberg） 七桥问题：
18世纪 30年代，流经东普鲁士 （ Prussia） 王国小城哥尼斯堡的一条河流 Pregel河中有两个小岛，小岛与两岸有七座桥相连,当地居民热衷于讨论如下问题：一个散步者能否从某处出发，依次走过每座桥恰好一次，再回到原出发处？
2009-7-26 9
运 筹 学 Operations Research
1736年，瑞士数学家欧拉研究了此问题：
.Gh1 的行走路线不存在不是欧拉图，当然这样，根据是欧拉图吗？哥堡七桥问题
T
G?
2009-7-26 10
运 筹 学 Operations Research
欧拉为此曾撰文,Solutio Problematis ad geometrian
Situs Pertinentis》（ 依据几何位置的解题方法），阐述了欧拉图的判定的充分必要条件，即 Th1,是为历史上的第一篇图论论文,
欧拉以此而成为图论的创始人，被称为,图论之父,
（ father of graph theory）,
欧拉一生曾发表 886篇论文，出版近 90本著作，其中很多是在双目失明的生命的最后 20年完成的,
2009-7-26 11
运 筹 学 Operations Research
中国邮递员问题 （ Chinese Postman Problem,CPP）
一个邮递员投递信件必须走遍某街区的所有街道,任务完成后再回到邮局,问他应如何安排投递路线,才能使得所走路线最短？
这一问题由我国数学家、山东师范大学数学系教授管梅谷（ Kuan Mei Ko） 先生于 1962年首先提出，并给出了一个算法（奇偶点图上作业法），故在国际上被称为中国邮递员问题,
图论模型：
以街道为边,以街口 （ 街道与街道的交叉处 ） 为顶点,
以街道的长度为边的权作图 G.
2009-7-26 12
运 筹 学 Operations Research
奇偶点图上作业法,1962年,Kuan M-K
基本思想：
若 G是欧拉图,则 G含有一条欧拉环游,显然,此欧拉环游即为唯一最优投递路线；
若 G不是欧拉图 （ 包括半欧拉图和非欧拉图 ）,则 G不含有欧拉环游,故可行投递路线中必含有某些重复边,而且这些重复边显然必仅与 G的奇度顶点相关联,为使得投递路线最优,应设法使这些重复边的权之和最短,
在算法上,奇偶点图上作业法要求从某一个可行投递路线开始,不断修正之,直到满足最优性判断标准,即得最优投递路线,
2009-7-26 13
运 筹 学 Operations Research
初始可行投递路线的确定：
找出图 （ 半欧拉图和非欧拉图 ） G的所有奇度顶点,将其一一配对,
找出每一对奇度顶点之间的任一条路,将路上各边重复一次,
权不变,取新图 （ 已变为欧拉图 ） 中唯一的一条欧拉环游作为初始可行投递路线,
2009-7-26 14
运 筹 学 Operations Research
最优投递路线的判断标准：
（ 1） 图的每条边至多有一条重复边；
若某 条 边的重复边的条数 ≥ 2,则可从中去掉偶数条,使得此边至多有一条重复边,如此,并不改变顶点的奇偶性,即新图仍是欧拉图,且重复边的权之和变小,即新投递路线更优,
2009-7-26 15
运 筹 学 Operations Research
（ 2） 图的每个圈上的重复边的权之和不大于该圈的权的一半 （ 即重复边的权之和不大于未重复边的权之和 ）,
若某个圈上的重复边的权之和大于该圈的权的一半，即重复边的权之和大于未重复边的权之和，则可去掉重复边，
而将未重复边均重复一次,如此，并不改变顶点的奇偶性，
即新图仍是欧拉图，且重复边的权之和变小，即新投递路线更优,
2009-7-26 16
运 筹 学 Operations Research
投递路线的调整：
（ 1）若某条边的重复边的条数 ≥
2,则可从中去掉偶数条,使得此边至多有一条重复边；
（ 2）若某个圈上的重复边的权之和大于该圈的权的一半（即重复边的权之和大于未重复边的权之和），则可去掉重复边，
而将未重复边均重复一次,
根据以上讨论，设计算法如下：
2009-7-26 17
运 筹 学 Operations Research
2009-7-26 18
运 筹 学 Operations Research
例 1 求解中国邮递员问题：（ s为邮局）
.
.
312431
3241
上的边各重复一次，将路分别配对与，与解：将奇顶点
vvvvvv
vvvv
2009-7-26 19
运 筹 学 Operations Research
.31 vv去掉重复边
.12431 vvvvv调整圈此时，图中的欧拉环游即为最优投递路,▌
2009-7-26 20
运 筹 学 Operations Research
Ex：
解：
▌
2009-7-26 21
运 筹 学 Operations Research
§ 6.3 over
运 筹 学 Operations Research
§ 6.3 中国邮递员问题（ CPP）
欧拉迹 （ Euler trail）,经过图的每条边恰好一次的迹；
欧拉环游 （ Euler tour）,闭的欧拉迹；
欧拉图 （ Euler graph）,含有欧拉环游的图；
半欧拉图 （ SemiEuler graph）,仅含有欧拉迹,不含有欧拉环游的图；
非欧拉图（ NonEuler graph）,otherwise,
2009-7-26 2
运 筹 学 Operations Research
2009-7-26 3
运 筹 学 Operations Research
.
)u le r1 7 3 6(1
恰含有两个奇顶点是半欧拉图不含有奇顶点；是欧拉图为非空连通图，则设，
GG
GG
GETh
证,（ 1）
（ 2）
▌
2009-7-26 4
运 筹 学 Operations Research
.)1(为欧拉图，则若图 G
几个结论：
.2)(21h
Vv
vdTG 有，由必为连通图，证,?
.,
);3()2(
,都为偶数为欧拉图为奇数为欧拉图
nmK
K
nm?
它们何时为半欧拉图？
(3)非平凡树 树必非欧拉图,
证,∵ 非平凡树均至少有两个 叶,▌
树可否为半欧拉图？
▌
2009-7-26 5
运 筹 学 Operations Research
,一笔画,问题,
能否一笔 （ 无重笔 ） 画出整个图？
对欧拉图,任选一个顶点为始点和终点,即可一笔画；
对半欧拉图,任选两个奇度顶点的一个为始点,另一个为终点,即可一笔画；
对非欧拉图，不可一笔画,
2009-7-26 6
运 筹 学 Operations Research
总统头像一笔画：
美国画家 Oscar Berger曾以其非凡的绘画技巧，独创一格地把,一笔画,原理运用到人物肖像画领域．在他的笔下，
从华盛顿到里根的前后 40位美国总统的脸部特征被刻画得惟妙惟肖，甚至喜怒哀乐的表情也都和盘托出了．下面是几幅中国读者比较熟悉的总统头像：
2009-7-26 7
运 筹 学 Operations Research
更令人吃惊的是，他竟是把一气呵成地一笔画出来的,Berger可谓开风气之先，在其作品示范与影响之下，绘画界居然刮起了一股不大不小的漫画名人之风．
2009-7-26 8
运 筹 学 Operations Research
哥尼斯堡（ Knigsberg） 七桥问题：
18世纪 30年代，流经东普鲁士 （ Prussia） 王国小城哥尼斯堡的一条河流 Pregel河中有两个小岛，小岛与两岸有七座桥相连,当地居民热衷于讨论如下问题：一个散步者能否从某处出发，依次走过每座桥恰好一次，再回到原出发处？
2009-7-26 9
运 筹 学 Operations Research
1736年，瑞士数学家欧拉研究了此问题：
.Gh1 的行走路线不存在不是欧拉图，当然这样，根据是欧拉图吗？哥堡七桥问题
T
G?
2009-7-26 10
运 筹 学 Operations Research
欧拉为此曾撰文,Solutio Problematis ad geometrian
Situs Pertinentis》（ 依据几何位置的解题方法），阐述了欧拉图的判定的充分必要条件，即 Th1,是为历史上的第一篇图论论文,
欧拉以此而成为图论的创始人，被称为,图论之父,
（ father of graph theory）,
欧拉一生曾发表 886篇论文，出版近 90本著作，其中很多是在双目失明的生命的最后 20年完成的,
2009-7-26 11
运 筹 学 Operations Research
中国邮递员问题 （ Chinese Postman Problem,CPP）
一个邮递员投递信件必须走遍某街区的所有街道,任务完成后再回到邮局,问他应如何安排投递路线,才能使得所走路线最短？
这一问题由我国数学家、山东师范大学数学系教授管梅谷（ Kuan Mei Ko） 先生于 1962年首先提出，并给出了一个算法（奇偶点图上作业法），故在国际上被称为中国邮递员问题,
图论模型：
以街道为边,以街口 （ 街道与街道的交叉处 ） 为顶点,
以街道的长度为边的权作图 G.
2009-7-26 12
运 筹 学 Operations Research
奇偶点图上作业法,1962年,Kuan M-K
基本思想：
若 G是欧拉图,则 G含有一条欧拉环游,显然,此欧拉环游即为唯一最优投递路线；
若 G不是欧拉图 （ 包括半欧拉图和非欧拉图 ）,则 G不含有欧拉环游,故可行投递路线中必含有某些重复边,而且这些重复边显然必仅与 G的奇度顶点相关联,为使得投递路线最优,应设法使这些重复边的权之和最短,
在算法上,奇偶点图上作业法要求从某一个可行投递路线开始,不断修正之,直到满足最优性判断标准,即得最优投递路线,
2009-7-26 13
运 筹 学 Operations Research
初始可行投递路线的确定：
找出图 （ 半欧拉图和非欧拉图 ） G的所有奇度顶点,将其一一配对,
找出每一对奇度顶点之间的任一条路,将路上各边重复一次,
权不变,取新图 （ 已变为欧拉图 ） 中唯一的一条欧拉环游作为初始可行投递路线,
2009-7-26 14
运 筹 学 Operations Research
最优投递路线的判断标准：
（ 1） 图的每条边至多有一条重复边；
若某 条 边的重复边的条数 ≥ 2,则可从中去掉偶数条,使得此边至多有一条重复边,如此,并不改变顶点的奇偶性,即新图仍是欧拉图,且重复边的权之和变小,即新投递路线更优,
2009-7-26 15
运 筹 学 Operations Research
（ 2） 图的每个圈上的重复边的权之和不大于该圈的权的一半 （ 即重复边的权之和不大于未重复边的权之和 ）,
若某个圈上的重复边的权之和大于该圈的权的一半，即重复边的权之和大于未重复边的权之和，则可去掉重复边，
而将未重复边均重复一次,如此，并不改变顶点的奇偶性，
即新图仍是欧拉图，且重复边的权之和变小，即新投递路线更优,
2009-7-26 16
运 筹 学 Operations Research
投递路线的调整：
（ 1）若某条边的重复边的条数 ≥
2,则可从中去掉偶数条,使得此边至多有一条重复边；
（ 2）若某个圈上的重复边的权之和大于该圈的权的一半（即重复边的权之和大于未重复边的权之和），则可去掉重复边，
而将未重复边均重复一次,
根据以上讨论，设计算法如下：
2009-7-26 17
运 筹 学 Operations Research
2009-7-26 18
运 筹 学 Operations Research
例 1 求解中国邮递员问题：（ s为邮局）
.
.
312431
3241
上的边各重复一次，将路分别配对与，与解：将奇顶点
vvvvvv
vvvv
2009-7-26 19
运 筹 学 Operations Research
.31 vv去掉重复边
.12431 vvvvv调整圈此时，图中的欧拉环游即为最优投递路,▌
2009-7-26 20
运 筹 学 Operations Research
Ex：
解：
▌
2009-7-26 21
运 筹 学 Operations Research
§ 6.3 over
