画时以一个奇点为起点，另一个 奇点为终点
欧拉回路
经过图中所有边一次，且访问每个顶点至少一 次的一个回路，称为欧拉回路。
具有欧拉回路的图称为欧拉图。
注意：通过图中所有边一次且仅一次行遍所有 顶点的通路称为欧拉通路。
判断下列图形能否一笔画
图1
图3
图5
图2
图4
图6
下图是一个公园的平面图，要使游人 走遍每一条路不重复，出口和入口应 设在哪儿？
中国邮递员问题
• 中国邮递员问题(Chinese Postman Problem, CPP)是由我国管梅谷教授于1962年
首先提出并发表的 • 例如：观察下列段道图
图（1）
图（2）
从邮局出发，走遍邮区的所有街道至少
一次再回到邮局，按照什么样的路线投
递邮件才能使总的路程最短？
投递路线 一笔画
欧拉回路
一天又一天，７座桥上走过了无数的行人。不知 从什么时候起，脚下的桥梁触发了人们的灵感，一个 有趣的问题在居民中传开了：谁能够一次走遍所有的 ７座桥，而且每座桥都只通过一次？
这个问题似乎不难，谁都乐意用它来测试一下自 己的智力。可是，谁也没有找到一条这样的路线。以 博学著称的大学教授们，也感到一筹莫展。"七桥问 题"难住了哥尼斯堡的所有居民。哥尼斯堡也因"七桥 问题"而出了名。
6
七桥问题
哥尼斯堡七桥
问题：如何不重复地走 完七桥后回到起点？
一笔画问题 如何将此图一笔画出？
7
欧拉的推理
欧拉这种处理问题 的方法标志着图论
的诞生
凡是一笔画中出现的交点处，线一出一进总 应该通过偶数条（偶点），只有作为起点和终点 的两点才有可能通过奇数条（奇点）。
欧拉（L.Euler,1707.4.151783.9.18）著名的数学家。生 于瑞士的巴塞尔，卒于彼得堡。 大部分时间在俄国和德国度过。 他早年在数学天才贝努里赏识 下开始学习数学, 17岁获得硕 士学位，毕业后研究数学,是数 学史上最高产的作家。在世发 表论文700多篇,去世后还留下 100多篇待发表。其论著几乎涉 及所有数学分支。
观察下列图形，完成统计表
可以一笔画的图形
不能一笔画的图形
图形序号 奇点个数 偶点个数
图形序号 奇点个数 偶点个数
图1
图2
图3
图4
图5
图6
图7
图8
不连通的图形不能一笔画
连通的图 形有可能 一笔画
奇点个数超过两个的连通图 形不能一笔画
全都是偶点的连 通图可以一笔画
有两个奇点的连 通图可以一笔画
画时以任一点为起点，最后仍回 到该点
最理想的投递路线，就是该段道图是一条欧拉回路。 图（2）的投递路线如下图（3）。
含有奇点的段道图不能一笔画出，有些道路需要重复 走两次的都要添上一条弧。图（1）添弧后如图（4）。
图（3）
图（4）
• 定理1 一个能够不重复的一笔画出的连通图中 ，所以的点一定都是偶点。
• 定理2 没有奇点的连通图一定能够从任意一点 开始不重复的一笔画出。
3
欧拉的解法
哥尼斯堡七桥问题引起了大数学家欧 拉的兴趣。他知道，如果沿着所有可能 的路线都走一次的话，一共要走5040次 。就算是一天走一次，也需要13年多的 时间。实际上，欧拉只用了几天的时间 就解决了七桥问题。
5
欧拉的想法是：两岸的陆地与河中的小岛 ，都是桥梁的连接点，它们的大小、形状均与 问题本身无关。因此，不妨把它们看作是4个 点。7座桥是7条必须经过的路线，它们的长短 、曲直，也与问题本身无关。因此，不妨任意 画7条线来表示它们。就这样，欧拉将七桥问 题抽象成了一个“一笔画”问题，从而否定了 问题的答案。
• 类似的还有送奶工送奶问题。
• 欧拉在数学、物理、天文、建筑 以至音乐、哲学方面都取得了辉 煌的成就。在数学的各个领域， 常常见到以欧来命名的公式、定 理、和重要常数。课本上常见的 如π、i、e、sin、cos、tg、△x 、Σ、f(x)等，都是他创立并推 广的。欧拉还首先完成了月球绕 地球运动的精确理论，创立了分 析力学、刚体力学等力学学科， 深化了望远镜、显微镜的设计计 算理论。
• 最优投递路线 重复的路最短 添弧的总长 度最短
• 添弧最短的条件 （1）没有重叠的添弧 （2）每一个圈上添弧的总长度不超过圈长的一
半 • 最短的一组添弧称为最优ห้องสมุดไป่ตู้。
案例：西北大学的洒水车要给主要路 面洒水，该如何确定行车路线？
• 洒水车要给主要路面洒水，也就意 味着行车路线必需经过图示所有的 路面至少一次。这类似于邮路问题 。
哥尼斯堡七桥问题
教学目标
➢ 知道一笔画问题的提法 ➢ 掌握段道图能否一笔画的判断方法 ➢ 会用添弧的方法求最优解
重点和难点
➢ 最优投递路线的求法
哥尼斯堡七桥问题
哥尼斯堡是位于波罗的海东岸一座古老而美丽的 城市，布勒格尔河的两条支流在这里汇合，然后横贯 全城，流入大海。河心有一个小岛。河水把城市分成 了４块，于是，人们建造了７座各具特色的桥，把哥 尼斯堡连成一体。