哥尼斯堡七桥问题学习资料课件

哥尼斯堡七桥问题哥尼斯堡七桥问题1知道一笔画问题的提法掌握段道图能否一笔画的判断方法会用添弧的方法求最优解最优投递路线的求法教学目标重点和难点知道一笔画问题的提法教学目标重点和难点2哥尼斯堡七桥问题学习资料课件3哥尼斯堡七桥问题学习资料课件45欧拉的解法

哥尼斯堡七桥问题引起了大数学家欧拉的兴趣。他知道，如果沿着所有可能的路线都走一次的话，一共要走5040次。就算是一天走一次，也需要13年多的时间。实际上，欧拉只用了几天的时间就解决了七桥问题。

5欧拉的解法哥尼斯堡七桥问题引起了大数学56

欧拉的想法是：两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，不妨把它们看作是4个点。7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，不妨任意画7条线来表示它们。就这样，欧拉将七桥问题抽象成了一个“一笔画”问题，从而否定了问题的答案。6欧拉的想法是：两岸的陆地与河中的小岛，67七桥问题

哥尼斯堡七桥问题：如何不重复地走完七桥后回到起点？一笔画问题如何将此图一笔画出？7七桥问题哥尼斯堡七桥一笔画问题7欧拉的推理

凡是一笔画中出现的交点处，线一出一进总应该通过偶数条（偶点），只有作为起点和终点的两点才有可能通过奇数条（奇点）。欧拉这种处理问题的方法标志着图论的诞生欧拉的推理凡是一笔画中出现的交点处，线一出一进总欧8

欧拉（L.Euler,1707.4.15-1783.9.18）著名的数学家。生于瑞士的巴塞尔，卒于彼得堡。大部分时间在俄国和德国度过。他早年在数学天才贝努里赏识下开始学习数学,17岁获得硕士学位，毕业后研究数学,是数学史上最高产的作家。在世发表论文700多篇,去世后还留下100多篇待发表。其论著几乎涉及所有数学分支。欧拉（L.Euler,179欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领域，常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如π、i、e、sin、cos、tg、△x、Σ、f(x)等，都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论，创立了分析力学、刚体力学等力学学科，深化了望远镜、显微镜的设计计算理论。欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的10观察下列图形，完成统计表图7图5图1图8图6图4图3图2可以一笔画的图形不能一笔画的图形图形序号奇点个数偶点个数

图形序号奇点个数偶点个数

观察下列图形，完成统计表图7图5图1图8图6图4图3图2可11不连通的图形不能一笔画

连通的图形有可能一笔画全都是偶点的连通图可以一笔画

奇点个数超过两个的连通图形不能一笔画画时以任一点为起点，最后仍回到该点画时以一个奇点为起点，另一个奇点为终点有两个奇点的连通图可以一笔画

不连通的图形不能一笔画连通的图形有可能一笔画全都是偶点的12欧拉回路

经过图中所有边一次，且访问每个顶点至少一次的一个回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。

注意：通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。欧拉回路经过图中所有边一次，且访问每个顶点至少13判断下列图形能否一笔画图5图4图3图2图6图1判断下列图形能否一笔画图5图4图3图2图6图114下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入口应设在哪儿？下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入15中国邮递员问题中国邮递员问题(ChinesePostmanProblem,CPP)是由我国管梅谷教授于1962年首先提出并发表的例如：观察下列段道图

从邮局出发，走遍邮区的所有街道至少

一次再回到邮局，按照什么样的路线投

递邮件才能使总的路程最短？图（1）图（2）中国邮递员问题中国邮递员问题(ChinesePostman16

投递路线一笔画欧拉回路

最理想的投递路线，就是该段道图是一条欧拉回路。图（2）的投递路线如下图（3）。

含有奇点的段道图不能一笔画出，有些道路需要重复走两次的都要添上一条弧。图（1）添弧后如图（4）。图（3）图（4）投递路线一笔画17定理1一个能够不重复的一笔画出的连通图中，所以的点一定都是偶点。定理2没有奇点的连通图一定能够从任意一点开始不重复的一笔画出。最优投递路线重复的路最短添弧的总长度最短添弧最短的条件（1）没有重叠的添弧（2）每一个圈上添弧的总长度不超过圈长的一半最短的一组添弧称为最优解。

定理1一个能够不重复的一笔画出的连通图中，所以的点一定都18案例：西北大学的洒水车要给主要路面洒水，该如何确定行车路线？案例：西北大学的洒水车要给主要路面洒水，该如何确定行车路线？19洒水车要给主要路面洒水，也就意味着行车路线必需经过图示所有的路面至少一次。这类似于邮路问题。类似的还有送奶工送奶问题。洒水车要给主要路面洒水，也就意味着行车路线必需经过图示所有的20哥尼斯堡七桥问题哥尼斯堡七桥问题21知道一笔画问题的提法掌握段道图能否一笔画的判断方法会用添弧的方法求最优解最优投递路线的求法教学目标重点和难点知道一笔画问题的提法教学目标重点和难点22哥尼斯堡七桥问题学习资料课件23哥尼斯堡七桥问题学习资料课件2425欧拉的解法

哥尼斯堡七桥问题引起了大数学家欧拉的兴趣。他知道，如果沿着所有可能的路线都走一次的话，一共要走5040次。就算是一天走一次，也需要13年多的时间。实际上，欧拉只用了几天的时间就解决了七桥问题。

5欧拉的解法哥尼斯堡七桥问题引起了大数学2526

欧拉的想法是：两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，不妨把它们看作是4个点。7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，不妨任意画7条线来表示它们。就这样，欧拉将七桥问题抽象成了一个“一笔画”问题，从而否定了问题的答案。6欧拉的想法是：两岸的陆地与河中的小岛，2627七桥问题

哥尼斯堡七桥问题：如何不重复地走完七桥后回到起点？一笔画问题如何将此图一笔画出？7七桥问题哥尼斯堡七桥一笔画问题27欧拉的推理

凡是一笔画中出现的交点处，线一出一进总应该通过偶数条（偶点），只有作为起点和终点的两点才有可能通过奇数条（奇点）。欧拉这种处理问题的方法标志着图论的诞生欧拉的推理凡是一笔画中出现的交点处，线一出一进总欧28

欧拉（L.Euler,1707.4.15-1783.9.18）著名的数学家。生于瑞士的巴塞尔，卒于彼得堡。大部分时间在俄国和德国度过。他早年在数学天才贝努里赏识下开始学习数学,17岁获得硕士学位，毕业后研究数学,是数学史上最高产的作家。在世发表论文700多篇,去世后还留下100多篇待发表。其论著几乎涉及所有数学分支。欧拉（L.Euler,1729欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领域，常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如π、i、e、sin、cos、tg、△x、Σ、f(x)等，都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论，创立了分析力学、刚体力学等力学学科，深化了望远镜、显微镜的设计计算理论。欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的30观察下列图形，完成统计表图7图5图1图8图6图4图3图2可以一笔画的图形不能一笔画的图形图形序号奇点个数偶点个数

图形序号奇点个数偶点个数

观察下列图形，完成统计表图7图5图1图8图6图4图3图2可31不连通的图形不能一笔画

连通的图形有可能一笔画全都是偶点的连通图可以一笔画

奇点个数超过两个的连通图形不能一笔画画时以任一点为起点，最后仍回到该点画时以一个奇点为起点，另一个奇点为终点有两个奇点的连通图可以一笔画

不连通的图形不能一笔画连通的图形有可能一笔画全都是偶点的32欧拉回路

经过图中所有边一次，且访问每个顶点至少一次的一个回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。

注意：通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。欧拉回路经过图中所有边一次，且访问每个顶点至少33判断下列图形能否一笔画图5图4图3图2图6图1判断下列图形能否一笔画图5图4图3图2图6图134下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入口应设在哪儿？下图是一个公园的平面图，要使游人走遍每一条路不重复，出口和入35中国邮递员问题中国邮递员问题(ChinesePostmanProblem,CPP)是由我国管梅谷教授于1962年首先提出并发表的例如：观察下列段道图

从邮局出发，走遍邮区的所有街道至少

一次再回到邮局，按照什么样的路线投

递邮件才能使总的路程最短？图（1）图（2）中国邮递员问题中国邮递员问题(ChinesePostman36

投递路线一笔画欧拉回路

最理想的投递路线，就是该段道图是一条欧拉回路。图（2）的投递路线如下图（3）。

含有奇点的段道图不能一笔画出，有些道路需要重复走两次的都要添上一条弧。图（1）添弧后如图（4）。图（3）图（4）投递路线一笔画37定理1一个能够不重复的一笔画出的连通图中，所以的点一定都是偶点。定理2没有奇点的连通图一定能够从任意一点开始不重复的一笔画出。最优投递路线重复的路最短添弧的总长度最短添弧最短