运筹学 Operations Research §6.3中国邮递员问题(CPP) 欧拉迹( Euler trail):经过图的每条边恰好一次的迹; 欧拉环游( Euler tour):闭的欧拉迹; 欧拉图( Euler graph):含有欧拉环游的图; 半欧拉图( Semi Euler graph):仅含有欧拉迹,不含有欧拉 环游的图 非欧拉图( NonEuler graph): otherwise 欧拉图G 2021/2/20
2021/2/20 1 运 筹 学 Operations Research §6.3 中国邮递员问题（CPP） 欧拉迹（Euler trail）：经过图的每条边恰好一次的迹； 欧拉环游（Euler tour）：闭的欧拉迹； 欧拉图（Euler graph）：含有欧拉环游的图； 半欧拉图（SemiEuler graph）：仅含有欧拉迹，不含有欧拉 环游的图； 非欧拉图（NonEuler graph）：otherwise
运筹学 Operations Research 半欧拉图G 非欧控图G 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research
运筹学 Operations Research hl(1736,Euer)设G为非空连通图,则 G是欧拉图分G不含有奇顶点; G是半欧拉图分→G恰含有两个奇顶点 证:(1) (2) 起点 终点 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research . 1 (1736 uler ) 是半欧拉图 恰含有两个奇顶点 是欧拉图 不含有奇顶点； ， 设 为非空连通图，则 G G G G Th E G 证：（1） （2） ▌
运筹学 Operations Research 几个结论: (1)若图G为欧拉图,则E≥v 证:G必为连通图,由7h,26=∑()≥2v→E≥v (2)K,为欧拉图分1为奇数(v≥3); K为欧拉图分m,n都为偶数 它们何时为半欧拉图? (3)非平凡树树必非欧拉图 证:∵非平凡树均至少有两个叶.■ 树可否为半欧拉图? 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research (1)若图G为欧拉图，则 . 几个结论： h1 2 = ( ) 2 . vV 证：G必为连通图， 由T 有， d v , . (2) ( 3); , 为欧拉图 都为偶数 为欧拉图 为奇数 K m n K m n 它们何时为半欧拉图？ (3)非平凡树树必非欧拉图. 证：∵非平凡树均至少有两个叶.▌ 树可否为半欧拉图？ ▌
运筹学 Operations Research “一笔画”问题: 能否一笔(无重笔)画出整个图? 对欧拉图,任选一个顶点为始点和终点,即可一笔画 对半欧拉图,任选两个奇度顶点的一个为始点,另一个为终 点,即可一笔画; 对非欧拉图,不可一笔画 可一笔画 可一笔画 不可一笔画 2021/2/20
2021/2/20 5 运 筹 学 Operations Research “一笔画”问题： 能否一笔（无重笔）画出整个图？ 对欧拉图，任选一个顶点为始点和终点，即可一笔画； 对半欧拉图，任选两个奇度顶点的一个为始点，另一个为终 点，即可一笔画； 对非欧拉图，不可一笔画
运筹学 Operations Research 总统头像一笔画: 美国画家 Oscar Berger曾以其非凡的绘画技巧,独创一格 地把“一笔画”原理运用到人物肖像画领域.在他的笔下, 从华盛顿到里根的前后40位美国总统的脸部特征被刻画得惟 妙惟肖,甚至喜怒哀乐的表情也都和盘托出了.下面是几幅 中国读者比较熟悉的总统头像: 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research 总统头像一笔画： 美国画家Oscar Berger曾以其非凡的绘画技巧，独创一格 地把“一笔画”原理运用到人物肖像画领域．在他的笔下， 从华盛顿到里根的前后40位美国总统的脸部特征被刻画得惟 妙惟肖，甚至喜怒哀乐的表情也都和盘托出了．下面是几幅 中国读者比较熟悉的总统头像：
运筹学 Operations Research 更令人吃惊的是,他竞是把一气呵成地一笔画出来 的. Berger可谓开风气之先,在其作品示范与影响之下,绘 画界居然刮起了一股不大不小的漫画名人之风 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research 更令人吃惊的是，他竟是把一气呵成地一笔画出来 的．Berger可谓开风气之先，在其作品示范与影响之下，绘 画界居然刮起了一股不大不小的漫画名人之风．
运筹学 Operations Research 哥尼斯堡( Konigsberg)七桥问题: 18世纪30年代,流经东普鲁士( Prussia)王国小城哥 尼斯堡的一条河流 Prege河中有两个小岛,小岛与两岸有七 座桥相连当地居民热衷于讨论如下问题:一个散步者能否从 某处出发,依次走过每座桥恰好次,再回到原出发处? C D 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research 哥尼斯堡（Knigsberg）七桥问题： 18世纪30年代，流经东普鲁士（Prussia）王国小城哥 尼斯堡的一条河流Pregel河中有两个小岛，小岛与两岸有七 座桥相连.当地居民热衷于讨论如下问题：一个散步者能否从 某处出发，依次走过每座桥恰好一次，再回到原出发处？
运筹学 Operations Research 1736年,瑞士数学家欧拉研究了此问题: A B 哥堡七桥问题◇G是欧拉图吗? 根据Thl,G不是欧拉图,当然这样的行走路线不存在 2021/2/20
2021/2/20 9 运 筹 学 Operations Research 1736年，瑞士数学家欧拉研究了此问题： 根据 h1，G不是欧拉图，当然这样的行走路线不存在. 哥堡七桥问题 是欧拉图吗？ T G
运筹学 Operations Research 欧拉为此曾撰文《 Solutio problematis ad geometrian Situs pertinentis》(依据几何位置的解题方法),阐述 了欧拉图的判定的充分必要条件,即Th1,是为历史上的第 篇图论论文 欧拉以此而成为图论的创始人,被称为“图论之父 (father of graph theory 欧拉一生曾发表886篇论文,出版近90本著作,其中很 多是在双目失明的生命的最后20年完成的 2021/2/20 10
2021/2/20 10 运 筹 学 Operations Research 欧拉为此曾撰文《Solutio Problematis ad geometrian Situs Pertinentis》（依据几何位置的解题方法），阐述 了欧拉图的判定的充分必要条件，即Th1，是为历史上的第 一篇图论论文. 欧拉以此而成为图论的创始人，被称为“图论之父” （father of graph theory）. 欧拉一生曾发表886篇论文，出版近90本著作，其中很 多是在双目失明的生命的最后20年完成的