2 1 图形 汝A如安 函 奇，点个数 是否是欧拉图 可能的起，点(
课件网) 信息科技五年级下册 单元主题七 ：快递路线规划师 活动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. 只有两个奇点，其余都为偶点的连通图。 必须以一个奇点为起点，另一个奇点则是终点。 满足第一个条件，可在所示所有蓝 点中任选一个作起点， ... ...
