一笔画问题(课堂PPT).ppt

第九讲一笔画问题故事发生在18世纪的哥尼斯堡城.流经那里的一条河中有两个小岛，还有七座桥把这两个小岛与河岸联系起来，那里风景优美，游人众多.在这美丽的地方，人们议论着一个有趣的问题：一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？这个问题曾吸引了许多人，连大数学家欧拉也对这个问题产生了兴趣。最后，得出了一个非常重要的结论，你想知道吗？其实这就是“一笔画”问题，也是一种数学游戏，学完了下面的内容，也许你就能像欧拉那样解决“七桥问题”了。数学中，我们把由有限个点和连接这些点的线（线段或弧）所组成的图形叫做图（如图（a））；图中的点叫做图的结点；连接两结点的线叫做图的边.如图（b）中，有三个结点：E、F、G，四条边：线段EG、FG以及连接E、F的两段弧.从图（a）、（b）中可以看出，任意两点之间都有一条通路（即可以从其中一点出发，沿着图的边走到另一点，如A到I的通路为A→H→I或A→D→I…），这样的图，我们称为连通图；而下图中（c）的一些结点之间却不存在通路（如M与N），像这样的图就不是连通图。所谓图的一笔画，指的就是：从图的一点出发，笔不离纸，遍历每条边恰好一次，即每条边都只画一次，不准重复.从上图中容易看出：能一笔画出的图首先必须是连通图.但是否所有的连通图都可以一笔画出呢？下面，我们就来探求解决这个问题的方法。为了叙述的方便，我们把与奇数条边相连的结点叫做奇点，把与偶数条边相连的点称为偶点.如上图（a）中的八个结点全是奇点，上图（b）中E、F为奇点，G为偶点。容易知道，上图（b）可以一笔画出，即从奇点E出发，沿箭头所指方向，经过F、G、E，最后到达奇点F；同理，从奇点F出发也可以一笔画出，最后到达奇点E.而从偶点G出发，却不能一笔画出.在七桥问题的图中有四个奇点，因此，欧拉断言：这个图无法一笔画出，也即游人不可能不重复地一次走遍七座桥.更进一步地，欧拉在解决七桥问题的同时彻底地解决了一笔画的问题，给出了下面的欧拉定理：①凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。②凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。③其他情况的图，都不能一笔画出。下面我们就来研究一笔画问题的具体应用：【例题1】在上图中，我们可以看出，一条线除了两端A、B外，其它地方的点指数均为2为偶点，所以在下面的讨论中，我们只关注图上的交点或顶点，而其它点忽略不计。下面四个图形能一笔画出吗？请你试一试，你发现了什么？【例题2】下面各图能不能一笔画成？如果能应该怎样画？如果不能，最少需要添几笔使它能够一笔画出？解答：图（1）中无奇点，能一笔画出，从任意点开始再回到这一点，仅举一例：A→B→C→N→F→G→H→M→D→N→E→M→H；图（2）有两个奇点，可以从B开始到E结束，也可以从E开始到B结束，如：B→C→D→E→A→B→E；图（3）不能一笔画出有4个奇点，要想一笔画出至少应该添一笔，可以连接A、B，如图1，其它的任何两个奇点都可以。共有多少连法呢，你能列举出来吗？共有6种分别为AB、AC、AD、BC、BD、CD；图（4）不能一笔画出有8个奇点，要想一笔画出至少应该添3笔，方法有很多种，只要选出6个奇点两两一组，分成3组相连即可。如图2。说明：不能一笔画出的图形可以通过添笔画使它能够一笔画出，要想添的笔画最少，就应该从奇点入手，将任意两个奇点连线，直至剩下两个奇点。把其余的每两个奇点一组，每组连一条线，这样就可以了。【例题3】图中是一个公园的道路平面图，要使游客走遍每条路且不重复，问出、入口应设在哪里？【例题4】下图是某地区所有街道的平面图.甲、乙二人同时分别从A、B出发，以相同的速度走遍所有的街道，最后到达C.如果允许两人在遵守规则的条件下可以选择最短路径的话，问两人谁能最先到达C？【例题5】下图是一个公园的平面图.要使游客走遍每条路而不重复，问出入口应设在哪里？【例题6】一张纸上画有如下图所示的图，你能否用剪刀一次连续剪下图中的三个正方形和两个三角形？【例题7】右图是一个街区公园道路的平面图，线段表示甬路，小明在A点，小刚在B点，两人比赛看谁能够先跑完所有的小路到达出口。已知两人速度相同，谁能最终获胜呢？【例题8】下图是某校专业教室的平面图，学生能否不重复地穿过每一扇门，如果能应该从哪儿走起，并给出一种路线。总结：一笔画的问题，给出了下面的欧拉定理：①凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。②凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。③其他情况的图，都不能一笔画出。通过这道题的分析解答过程我们发现，根据需要画出简