一笔画问题学习.pptx

《一笔画问题学习.pptx》由会员分享，可在线阅读，更多相关《一笔画问题学习.pptx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 故事发生在18世纪的哥尼斯堡城.流经那里的一条河中有两个小岛，还有七座桥把这两个小岛与河岸联系起来，那里风景优美，游人众多.在这美丽的地方，人们议论着一个有趣的问题：一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？这个问题曾吸引了许多人，连大数学家欧拉也对这个问题产生了兴趣。最后，得出了一个非常重要的结论，你想知道吗？其实这就是“一笔画”问题，也是一种数学游戏，学完了下面的内容，也许你就能像欧拉那样解决“七桥问题”了。第1页/共26页 欧拉解决这个问题的方法非常巧妙.他认为：人们关心的只是一次不重复地走遍这七座桥，而并不关心桥的长短和岛的大小，因此，岛和岸都可以看作一个点，而桥则

2、可以看成是连接这些点的一条线.这样，一个实际问题就转化为一个几何图形能否一笔画出的问题了.那么，什么叫一笔画？什么样的图可以一笔画出？欧拉又是如何彻底证明七桥问题的不可能性呢？下面，我们就来介绍这一方面的简单知识。第2页/共26页 数学中，我们把由有限个点和连接这些点的线（线段或弧）所组成的图形叫做图（如图（a）；图中的点叫做图的结点；连接两结点的线叫做图的边.如图（b）中，有三个结点：E、F、G，四条边：线段EG、FG以及连接E、F的两段弧.从图（a）、（b）中可以看出，任意两点之间都有一条通路（即可以从其中一点出发，沿着图的边走到另一点，如A到I的通路为AHI或ADI），这样的图，我们称为

3、连通图；而下图中（c）的一些结点之间却不存在通路（如M与N），像这样的图就不是连通图。第3页/共26页 所谓图的一笔画，指的就是：从图的一点出发，笔不离纸，遍历每条边恰好一次，即每条边都只画一次，不准重复.从上图中容易看出：能一笔画出的图首先必须是连通图.但是否所有的连通图都可以一笔画出呢？下面，我们就来探求解决这个问题的方法。为了叙述的方便，我们把与奇数条边相连的结点叫做奇点，把与偶数条边相连的点称为偶点.如上图（a）中的八个结点全是奇点，上图（b）中E、F为奇点，G为偶点。容易知道，上图（b）可以一笔画出，即从奇点E出发，沿箭头所指方向，经过F、G、E，最后到达奇点F；同理，从奇点F出发也

4、可以一笔画出，最后到达奇点E.而从偶点G出发，却不能一笔画出.第4页/共26页 在七桥问题的图中有四个奇点，因此，欧拉断言：这个图无法一笔画出，也即游人不可能不重复地一次走遍七座桥.更进一步地，欧拉在解决七桥问题的同时彻底地解决了一笔画的问题，给出了下面的欧拉定理：凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。其他情况的图，都不能一笔画出。下面我们就来研究一笔画问题的具体应用：第5页/共26页【例题1】在上图中，我们可以看出，一条线除了两

5、端A、B外，其它地方的点指数均为2为偶点，所以在下面的讨论中，我们只关注图上的交点或顶点，而其它点忽略不计。下面四个图形能一笔画出吗？请你试一试，你发现了什么？分析：经过试画，以及对图上交点进行分析，我们发现：图（1）可以一笔画出，A、B、C、D、E全为偶点，路线为A C DE C BA，从A点出发，又回到了A点，其实从任一点出发都可以一笔画出并回到这一点。图（2）可以一笔画出，A、C为奇点，B、D为偶点，路线可为ADCBAC，还有很多种走法，也可以从C出发最后到A，经过尝试，在有两个奇点时，可以一笔画出，若以一个奇点为起点，那么一定以另一个奇点为终点。图（3）不能一笔画出，A、B、C、D均为

6、奇点，E为偶点。图（4）不能一笔画出，A、B、C、D、E、F均为奇点，G为偶点。解答：图（1）能一笔画出，无奇点，可以从任一点开始，一笔画出，再回到这一点；图（2）能一笔画出，有两个奇点A、C，可以从其中一个奇点开始到另一个奇点结束；图（3）不能一笔画出，有4个奇点；图（4）不能一笔画出，有6个奇点。看来能否一笔画出与奇点个数有直接关系，你总结出规律了吗？说明：在连通图中，（1）若奇点的个数为0个，能够一笔画出，可以从任一点开始，一笔画出，最后回到这一点；若奇点的个数为2个，能够一笔画出，且必从其中一个奇点开始到另一个奇点结束；（2）若奇点的个数多于2个，这个图形就不能一笔画出。第6页/共26

7、页【例题2】下面各图能不能一笔画成？如果能应该怎样画？如果不能，最少需要添几笔使它能够一笔画出？分析：图（1）全是偶点，无奇点，能一笔画成，从任意点开始即可；图（2）只有B、E两个奇点，其它均为偶点，可以一笔画出，注意从一奇点开始到另一奇点结束；图（3）有A、B、C、D四个奇点，不能一笔画出，要想一笔画出，至少应该减少两个奇点，所以应该将上述四点中，任两点之间加一条线，使之成为偶点；图（4）中有A、B、C、D、E、F、G、H八个奇点，不能一笔画出，至少应该减少6个奇点，所以应该从8个奇点中选出6个，两两一组，连三条线，使它们变为偶点。第7页/共26页解答：图（1）中无奇点，能一笔画出，从任意点

8、开始再回到这一点，仅举一例：ABCNFGHMDNEMH；图（2）有两个奇点，可以从B开始到E结束，也可以从E开始到B结束，如：BCDEABE；图（3）不能一笔画出有4个奇点，要想一笔画出至少应该添一笔，可以连接A、B，如图1，其它的任何两个奇点都可以。共有多少连法呢，你能列举出来吗？共有6种分别为AB、AC、AD、BC、BD、CD；图（4）不能一笔画出有8个奇点，要想一笔画出至少应该添3笔，方法有很多种，只要选出6个奇点两两一组，分成3组相连即可。如图2。说明：不能一笔画出的图形可以通过添笔画使它能够一笔画出，要想添的笔画最少，就应该从奇点入手，将任意两个奇点连线，直至剩下两个奇点。把其余的每

9、两个奇点一组，每组连一条线，这样就可以了。第8页/共26页【例题3】图中是一个公园的道路平面图，要使游客走遍每条路且不重复，问出、入口应设在哪里？分析与解 依据题意可知，此题实际是一笔画问题。由于要设出口和入口，所以首先应确定有没有奇点，若有，有几个。因为图中只有E、I两个奇点，所以该道路图可以一笔画，只要将出、入口分别设在这两个点，游客就可以从入口处进入公园，不重复地走遍所有道路，而且从出口处离开公园。第9页/共26页【例题4】下图是某地区所有街道的平面图.甲、乙二人同时分别从A、B出发，以相同的速度走遍所有的街道，最后到达C.如果允许两人在遵守规则的条件下可以选择最短路径的话，问两人谁能最

10、先到达C？分析与解答本题要求二人都必须走遍所有的街道最后到达C，而且两人的速度相同.因此，谁走的路程少，谁便可以先到达C。容易知道，在题目的要求下，每个人所走路程都至少是所有街道路程的总和。仔细观察上图，可以发现图中有两个奇点：A和C.这就是说，此图可以以A、C两点分别作为起点和终点而一笔画成.也就是说，甲可以从A出发，不重复地走遍所有的街道，最后到达C；而从B出发的乙则不行.因此，甲所走的路程正好等于所有街道路程的总和，而乙所走的路程则必定大于这个总和，这样甲先到达C。第10页/共26页【例题5】下图是一个公园的平面图.要使游客走遍每条路而不重复，问出入口应设在哪里？分析与解答本题实际上是这

11、个图以哪两点为起点和终点一笔画出的问题.观察左图，可以发现仅有两个奇点：H与B点.因此，出入口应分别设在H点与B点.第11页/共26页【例题6】一张纸上画有如下图所示的图，你能否用剪刀一次连续剪下图中的三个正方形和两个三角形？分析与解答一次连续剪下图中的三个正方形和两个三角形，必须要求剪刀连续剪过图中所有的线.即上述问题实质上是这个图能否一笔画出的问题。显然，图中有两个奇点，因此可以一笔画出，剪刀所走的路线可以是：ABCDEFGEIGHAIC.这样，就能用剪刀一次连续剪下三个正方形和两个三角形。第12页/共26页【例题7】右图是一个街区公园道路的平面图，线段表示甬路，小明在A点，小刚在B点，两

12、人比赛看谁能够先跑完所有的小路到达出口。已知两人速度相同，谁能最终获胜呢？分析：先让我们一起来观察一下这个街区公园平面图，可以看出上面只有两个奇点，一个在A点，一个在出口，说明这个平面图可以一笔画出，从一个奇点出发在另一个奇点处结束。还原到实际情况中也就是可以从A点出发，不重复地走完所有的小路，到达出口。B点是个偶点，要想走完所有的小路到达出口，必然要重复，也就是所走的总路程就多，又因为小明与小刚两人速度相同，所以谁走的路程多谁就会输，谁走的路程少谁就会赢。解答：街区平面图中只有A点和出口是奇点，小明从A点出发可以不重复地走完所有的小路到达出口，而小刚在B点，要想走完所有的路到达出口，需要走重

13、复路，两人速度相同小刚走的路多，所以小明能够获胜。说明：一笔画问题在生活中有很好的应用，但解决问题的方法是一样的，都是通过对图中进行奇点分析来解决的。第13页/共26页【例题8】下图是某校专业教室的平面图，学生能否不重复地穿过每一扇门，如果能应该从哪儿走起，并给出一种路线。分析：这道题的关键是能否不重复地穿过每一扇门，而对于进入哪一个专业教室没有要求，所以我们不妨根据各扇门的连接情况，画出路线图，用点表示专业教室和楼道，用线表示把各个教室和楼道连起来，如图所示。这样，我们就构造了一个连通图。通过观察不难发现，绘画和面塑两个教室所处的位置是奇点，其它均为偶点，所以可以从这两个教室出发穿过每一扇门

14、并最终到达另一教室。解答：可以不重复地穿过每扇门，若从绘画教室出发，到面塑教室结束，若从面塑教室出发，到绘画教室结束，路线有很多种，仅举一例，如右图：第14页/共26页总结：一笔画的问题，给出了下面的欧拉定理：凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。其他情况的图，都不能一笔画出。通过这道题的分析解答过程我们发现，根据需要画出简要意示图是非常重要的方法。利用这种方法可以让我们更快的找到解决问题的途径。同学们，本讲前面所提到的七座桥问题

15、，你能解答了吗？对！我们把陆地和小岛看成点，把相互连接的桥看成线，画出示意图如下：不难发现，有4个奇点，所以不能一次不重复的走完所有的桥。你的想法与欧拉一样，如果你能用数学方法解决实际生活问题，相信你会与数学家一样伟大！第15页/共26页练习题1.下面的图形能否一笔画出？如果能，应怎样画？不能的请你把它改成一笔画？分析：这个问题可以通过判断图形奇数点个数来进行判断。如果不能一笔画成的，可以通过改变奇数点个数来实现图形的一笔画。具体步骤：解：图（1）有两个奇数点，可以一笔画成。画时，必须以其中一个奇数点为起点，另一个奇数点为终点。图（2）没有奇数点，可以一笔画成。画时，可以以任意点为起点。第16

16、页/共26页图（3）有两个奇点，可以一笔画成。画时，必须以其中一个奇点为起点，另一个奇点为终点。图（4）有两个奇点，可以一笔画成。画时，必须以其中一个奇点为起点，另一个奇点为终点。图（5）有六个奇点，不能一笔画成。改成奇点个数为2的图形：图（6）有四个奇点，不能一笔画成。改成奇点个数为2的图形：第17页/共26页2下面各图最少需要几笔才能画出？解答：图（1）共有6个奇点，最少需要三笔画出；图（2）共有2个奇点，最少需要一笔画出。第18页/共26页3下面各立体图形铁丝架至少需要几根铁丝才能做成？解答：图（1）共有6个奇点，需要三根铁丝才能作成；图（2）共有2个奇点，只需一根铁丝即可作成。第19页

17、/共26页4下图是一公园的平面图，要使游客走遍每一条路且不重复，问出入口应设在哪里？解答:出入口应分别设在两个奇点处，即A、B处。第20页/共26页5下面是一个公园的平面图，线段表示甬路，公园出、入口设在什么地方才能使游客一次不重复地走完所有小路？解答：从图上可以看出，只有A、C两点是奇点，其它点均为偶点，要想使游客一次不重复地走完所有小路，出入口应分别设在A、C两处，若A为入口，则C为出口；若C为入口，则A为出口。第21页/共26页6下图中的实线表示四驱车轨道，红车在A处，蓝车在B处，已知两车速度相同，哪辆车能够跑完所有轨道最先到达出口？解答：通过观察可以看出图上A、C处为奇点，其它地方均为

18、偶点，可以从A点出发不重复地跑完所有轨道到达入出口，若从B点出发需要重复，所以红车最先跑完全程后到达。第22页/共26页7下图是一个正方形小城镇道路示意图，警察晚上骑车巡逻，要从A点出发，穿过每条小路再回到A点，巡逻一次最少要走多少千米？解答：通过观察可看出图上有A、B、C、D、E、F共6个奇点，要从A点出发回到A点，应重复3条最短的小路，根据图中数据，可以看出重复AB、CF、DE这三条路能使路最短，所以巡逻一次最少要走：44+（1+2）3+2+13=16+9+2+3=30（千米）第23页/共26页8下图是植物园热带植物展厅，由六间展室组成，每相邻两室间有一扇门相通，请你设计一个出口，使参观者

19、能够从入口处（A处）进去，一次不重复地经过所有的门，最后由出口走出。解答：把各个展厅看成点，把门看成相连的展厅间连线，可以得以下面的示意图：从图中可以看出除了A点外，只有F点是奇点，所以出口设在F厅的右墙上。第24页/共26页9如下图所示，两条河流的交汇处有两个小岛和一个半岛，这座桥连接这岛与河岸，一个散步者能不能一次不重复地走遍这6座桥？如果不能需要在哪几架一座桥？如果能，给出一种走法。解答：我们把岸、小岛、半岛看成点，把连接的桥看成连线，这样画出示意图如下：通过观察可以看出只有岛1和半岛两处为奇点，其它均为偶点，所以可从这两处起一次不重复地走遍这6座桥，走法有很多种。仅举一例：岛1 岸（下）岛2半岛岸（上）岛1半岛。第25页/共26页谢谢您的观看！第26页/共26页