资源简介

2
1
图形
汝A如安 函
奇，点个数
是否是欧拉图
可能的起，点(共22张PPT)
信息科技五年级下册
单元主题七 ：快递路线规划师
活动3：不走重复的路径
授课教师：
情境导入——快递员小李的烦恼
快递员小李除了为小区提供派送服务，还要上门揽收居民发往全国的快递。这些居民位于不同的街道，为了提高效率，能否一次性揽收这些货而不走重复路（一笔画）呢？
什么是一笔画？
一笔画的界定
连通图是指从图形中任意一个交点，可以到达其他所有交点。
这是一个图形
线条+交点
一笔画的界定
在连通图中实现一笔画有两个要求：第一，画笔要经历所有的路线和交叉点；第二，同一条线路只能走一次，不能重复。
是一笔画图形
经历所有路线要重复，不是一笔画图形
一笔画的界定
探究实践：下面的图形中，哪些是一笔画图形，哪些不是？
是一笔画图形的打“√”，不是的打“×”。
√
×
一笔画图形的判断
18 世纪初，德国哥尼斯堡的公园里有七座桥，它们将河中两个岛屿与河岸连接起来。有人提出了一个具有挑战性的任务：一次走过所有桥，每座桥只能经过一次而且起点与终点必须是同一地点。
开动脑筋：你能完成这个任务吗？
一笔画图形的判断
著名数学家欧拉在挑战此任务时，将地图上的四个区域简化为四个点，七座桥则画作七条线段，从而把问题转化为“是否可以通过一笔画出这个图形”。
经过思考，欧拉认为这是不可能的。不仅如此，欧拉还得出了一笔画的判断条件。将原本需要穷举所有可能性的算法换成只需判断奇点个数的算法，快速得出结论，圆满地解答了这个难题。同时，欧拉开创了数学的一个新分支——图论。图论在计算机科学领域有着广泛的应用。
欧拉解决了一笔画的问题，因此，能够一笔画成的图形也被称作欧拉图。
信息链接
一笔画图形的判断
什么是奇点？我们把交点汇聚的线条数分奇数与偶数两种；
由奇数线条连接的点称为奇点。
一笔画图形的判断
满足以下两个条件之一的连通图可以实现一笔画：
1. 全部由偶点组成的连通图。
以任一偶点为起点，最后一定能以这个点为终点画完此图。
2. 只有两个奇点，其余都为偶点的连通图。
必须以一个奇点为起点，另一个奇点则是终点。
一笔画的判断条件
一笔画图形的判断
（1）找出图形的交叉点，并数一数其包含的交叉线。
判断一笔画的方法
3
3
2
2
探究实践：找出下面图形的交叉点，并标出每个交叉点包含的交叉线的数量。
4
4
4
4
2
2
2
2
2
2
一笔画图形的判断
（2）判断各交叉点的类型，并用不同符号、颜色等方式区分结果。
判断一笔画的方法
3
3
2
2
4
4
4
4
2
2
2
2
2
2
奇点
奇点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
一笔画图形的判断
（3）统计奇点和偶点的总数，判断该图形是否可以一笔画成，
并指出一笔画的起点和终点。
判断一笔画的方法
3
3
2
2
奇点
奇点
偶点
偶点
满足以下两个条件之一的连通图可以实现一笔画：
1. 全部由偶点组成的连通图。
以任一偶点为起点，最后一定能以这个点为终点画完此图。
2. 只有两个奇点，其余都为偶点的连通图。
必须以一个奇点为起点，另一个奇点则是终点。
满足第二个条件，可在所示两个橙色交叉点中任选一个作起点，另一个作终点。
奇点 ：2个
偶点 ：2个
一笔画图形的判断
（3）统计奇点和偶点的总数，判断该图形是否可以一笔画成，
并指出一笔画的起点和终点。
判断一笔画的方法
满足以下两个条件之一的连通图可以实现一笔画：
1. 全部由偶点组成的连通图。
以任一偶点为起点，最后一定能以这个点为终点画完此图。
2. 只有两个奇点，其余都为偶点的连通图。
必须以一个奇点为起点，另一个奇点则是终点。
满足第一个条件，可在所示所有蓝
点中任选一个作起点，同时也作终点。
奇点 ： 0个
偶点 ：10个
4
4
4
4
2
2
2
2
2
2
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
偶点
一笔画图形的判断
探究实践：在下列图中分别以每个交叉点作为起点，尝试一笔画绘制，并记录能完成一笔画的起点。
0
是
任意偶点
2
是
任意奇点
2
是
任意奇点
2
是
任意奇点
4
否
2
是
任意奇点
小结：奇点数量为0或2的连通图是欧拉图。
练习提升
1. 下面的图形中，哪些是一笔画图形，哪些不是？是一笔画图形的打“√”，不是的打“×”。
√
×
×
√
×
练习提升
2. 如果允许在七桥问题中再架一座桥，使游人能够不重复地走遍这八座桥，不要求回到起点，桥应该架在哪里？如果允许去掉七桥问题中的一座或几座桥，应该削减成几座桥才可以使游人不重复地走遍保留下来的桥？
奇点
奇点
奇点
奇点
如何架一座桥使得奇点数量为2？
偶点
偶点
削减几座桥可以使得奇点数量为0或2？
削减任意一座桥都可以使得奇点数量为2；任意去掉两座没有共同交点的桥可以使得奇点数量为0。
开拓视野
中国邮递员问题
邮递员每天从邮局出发，走遍该地区所有街道再返回邮局，他应如何安排送信的路线让总路程最短呢？这个问题由中国学者管梅谷在1960 年首先提出，并给出了解法——奇偶点图上作业法，被国际上统称为“中国邮递员问题”。
对于该问题，如果邮递员可以从邮局出发，走遍每条街道且不走重复路，最后回到邮局，这样的路线一定是距离最短的。这种解决问题的思路与我们熟悉的一笔画非常相似。
课堂总结
本节课我们在“快递员如何一次性揽收快递而不走重复路径”这一问题情境驱动下，学习了一笔画的界定、一笔画图形的判断以及一笔画在生活中的应用。
这是一堂信息科技与数学融合课程。我们需要从点和线的角度分析图形和连通图；我们需要严谨细致的根据奇点与偶点的数量确定一笔画路径的起点、终点和路线。一笔画问题通常用于图论中寻找不走重复路线的最短路径问题，在生活中则多运用于路径规划和图案设计，我们要学以致用、举一反三，将知识运用到解决生活问题中。
课堂总结
课后练习
小小设计师
A市要开发一个公园，现向广大市民征集设计稿。线条代表道路，交叉点代表景点，请你利用一笔画原理设计一条公园游览路线，确保游客不重复走就能逛遍所有景点。
单元回顾
同学们，下节课再见！

展开更多......

收起↑