第九讲 一笔画问题

第九讲一笔画问题•故事发生在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为偶点，所以在下面的讨论中，我们只关注图上的交点或顶点，而其它点忽略不计。下面四个图形能一笔画出吗？请你试一试，你发现了什么？分析：经过试画，以及对图上交点进行分析，我们发现：图（1）可以一笔画出，A、B、C、D、E全为偶点，路线为A→C→D→E→C→B→A，从A点出发，又回到了A点，其实从任一点出发都可以一笔画出并回到这一点。图（2）可以一笔画出，A、C为奇点，B、D为偶点，路线可为A→D→C→B→A→C，还有很多种走法，也可以从C出发最后到A，经过尝试，在有两个奇点时，可以一笔画出，若以一个奇点为起点，那么一定以另一个奇点为终点。图（3）不能一笔画出，A、B、C、D均为奇点，E为偶点。图（4）不能一笔画出，A、B、C、D、E、F均为奇点，G为偶点。解答：图（1）能一笔画出，无奇点，可以从任一点开始，一笔画出，再回到这一点；图（2）能一笔画出，有两个奇点A、C，可以从其中一个奇点开始到另一个奇点结束；图（3）不能一笔画出，有4个奇点；图（4）不能一笔画出，有6个奇点。看来能否一笔画出与奇点个数有直接关系，你总结出规律了吗？说明：在连通图中，（1）若奇点的个数为0个，能够一笔画出，可以从任一点开始，一笔画出，最后回到这一点；若奇点的个数为2个，能够一笔画出，且必从其中一个奇点开始到另一个奇点结束；（2）若奇点的个数多于2个，这个图形就不能一笔画出。•【例题2】下面各图能不能一笔画成？如果能应该怎样画？如果不能，最少需要添几笔使它能够一笔画出？分析：图（1）全是偶点，无奇点，能一笔画成，从任意点开始即可；图（2）只有B、E两个奇点，其它均为偶点，可以一笔画出，注意从一奇点开始到另一奇点结束；图（3）有A、B、C、D四个奇点，不能一笔画出，要想一笔画出，至少应该减少两个奇点，所以应该将上述四点中，任两点之间加一条线，使之成为偶点；图（4）中有A、B、C、D、E、F、G、H八个奇点，不能一笔画出，至少应该减少6个奇点，所以应该从8个奇点中选出6个，两两一组，连三条线，使它们变为偶点。•解答：图（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】图中是一个公园的道路平面图，要使游客走遍每条路且不重复，问出、入口应设在哪里？分析与解依据题意可知，此题实际是一笔画问题。由于要设出口和入口，所以首先应确定有没有奇点，若有，有几个。因为图中只有E、I两个奇点，所以该道路图可以一笔画，只要将出、入口分别设在这两个点，游客就可以从入口处进入公园，不重复地走遍所有道路，而且从出口处离开公园。•【例题4】下图是某地区所有街道的平面图.甲、乙二人同时分别从A、B出发，以相同的速度走遍所有的街道，最后到达C.如果允许两人在遵守规则的条件下可以选择最短路径的话，问两人谁能最先到达C？分析与解答本题要求二人都必须走遍所有的街道最后到达C，而且两人的速度相同.因此，谁走的路程少，谁便可以先到达C。容易知道，在题目的要求下，每个人所走路程都至少是所有街道路程的总和。仔细观察上图，可以发现图中有两个奇点：A和C.这就是说，此图可以以A、C两点分别作为起点和终点而一笔画成.也就是说，甲可以从A出发，不重复地走遍所有的街道，最后到达C；而从B出发的乙则不行.因此，甲所走的路程正好等于所有街道路程的总和，而乙所走的路程则必定大于这个总和，这样甲先到达C。•【例题5】下图是一个公园的平面图.要使游客走遍每条路而不重复，问出入口应设在哪里？分析与解答本题实际上是这个图以哪两点为起点和终点一笔画出的问题.观察左图，可以发现仅有两个奇点：H与B点.因此，出入口应分别设在H点与B点.•【例题6】一张纸上画有如下图所示的图，你能否用剪刀一次连续剪下图中的三个正方形和两个三角形？分析与解答一次连续剪下图中的三个正方形和两个三角形，必须要求剪刀连续剪过图中所有的线.即上述问题实质上是这个图能否一笔画出的问题。显然，图中有两个奇点，因此可以一笔画出，剪刀所走的路线可以是：A→B→C→D→E→F→G→E→I→G→H→A→I→C.这样，就能用剪刀一次连续剪下三个正方形和两个三角形。•【例题7】右图是一个街区公园道路的平面图，线段表示甬路，小明在A点，小刚在B点，两人比赛看谁能够先跑完所有的小路到达出口。已知两人速度相同，谁能最终获胜呢？分析：先让我们一起来观察一下这个街区公园平面图，可以看出上面只有两个奇点，一个在A点，一个在出口，说明这个平面图可以一笔画出，从一个奇点出发在另一个奇点处结束。还原到实际情况中也就是可以从A点出发，不重复地走完所有的小路，到达出口。B点是个偶点，要想走完所有的小路到达出口，必然要重复，也就是所走的总路程就多，又因为小明与小刚两人速度相同，所以谁走的路程多谁就会输，谁走的路程少谁就会赢。解答：街区平面图中只有A点和出口是奇点，小明从A点出发可以不重复地走完所有的小路到达出口，而小刚在B点，要想走完所有的路到达出口，需要走重复路，两人速度相同小刚走的路多，所以小明能够获胜。说明：一笔画问题在生活中有很好的应用，但解决问题的方法是一样的，都是通过对图中进行奇点分析来解决的。•【例题8】下图是某校专业教室的平面图，学生能否不重复地穿过每一扇门，如果能应该从哪儿走起，并给出一种路线。分析：这道题的关键是能否不重复地穿过每一扇门，而对于进入哪一个专业教室没有要求，所以我们不妨根据各扇门的连接情况，画出路线图，用点表示专业教室和楼道，用线表示把各个教室和楼道连起来，如图所示。这样，我们就构造了一个连通图。通过观察不难发现，绘画和面塑两个教室所处的位置是奇点，其它均为偶点，所以可以从这两个教室出发穿过每一扇门并最终到达另一教室。解答：可以不重复地穿过每扇门，若从绘画教室出发，到面塑教室结束，若从面塑教室出发，到绘画教室结束，路线有很多种，仅举一例，如右图：•总结：一笔画的问题，给出了下面的欧拉定理：•①凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。•②凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。•③其他情况的图，都不能一笔画出。•通过这道题的分析解答过程我们发现，根据需要画出简要意示图是非常重要的方法。利用这种方法可以让我们更快的找到解决问题的途径。•同学们，本讲前面所提到的七座桥问题，你能解答了吗？•对！我们把陆地和小岛看成点，把相互连接的桥看成线，画出示意图如下：•不难发现，有4个奇点，所以不能一次不重复的走完所有的桥。你的想法与欧拉一样，如果你能用数学方法解决实际生活问题，相信你会与数学家一样伟大！•练习题•1.下面的图形能否一笔画出？如果能，应怎样画？不能的请你把它改成一笔画？分析：这个问题可以通过判断图形奇数点个数来进行判断。如果不能一笔画成的，可以通过改变奇数点个数来实现图形的一笔画。具体步骤：解：图（1）有两个奇数点，可以一笔画成。画时，必须以其中一个奇数点为起点，另一个奇数点为终点。图（2）没有奇数点，可以一笔画成。画时，可以以任意点为起点。•图（3）有两个奇点，可以一笔画成。画时，必须以其中一个奇点为起点，另一个奇点为终点。•图（4）有两个奇点，可以一笔画成。画时，必须以其中一个奇点为起点，另一个奇点为终点。•图（5）有六个奇点，不能一笔画成。改成奇点个数为2的图形：•图（6）有四个奇点，不能一笔画成。改成奇点个数为2的图形：•2．下面各图最少需要几笔才能画出？•解答：•图（1）共有6个奇点，最少需要三笔画出；•图（2）共有2个奇点，最少需要一笔画出。•3．下面各立体图形铁丝架至少需要几根铁丝才能做成？•解答：•图（1）共有6个奇点，需要三根铁丝才能作成；•图（2）共有2个奇点，只需一根铁丝即可作成。•4．下图是一公园的平面图，要使游客走遍每一条路且不重复，问出入口应设在哪里？•解答:出入口应分别设在两个奇点处，即A、B处。•5．下面是一个公园的平面图，线段表示甬路，公园出、入口设在什么地方才能使游客一次不重复地走完所有小路？•解答：从图上可以看出，只有A、C两点是奇点，其它点均为偶点，要想使游客一次不重复地走完所有小路，出入口应分别设在A、C两处，若A为入口，则C为出口；若C为入口，则A为出口。•6．下图中的实线表示四驱车轨道，红车在A处，蓝车在B处，已知两车速度相同，哪辆车能够跑完所有轨道最先到