9.一笔和多笔画.docVIP

第九讲 一笔画和多笔画 问题1 你能一笔画出一个“田”字吗？所谓一笔画出的意思就是在一张纸上（不允许折叠）笔不离纸，而且每一笔划（或称线段）只能画一次，不准重复。对于“串”字或“品”字呢？结果会怎样？（参看图8－1） 　　通过各种尝试发现，“田”字总也不能一笔画成，而“串”字却可以一笔画成。由于“品”字中的三个“口”字不连在一起，显然也不能一笔画成。 　　我们把那些能一笔画成的图形叫一笔画。一笔画问题主要讨论什么样的图形可以一笔画成。 　　 例1 下列图形哪些能一笔画成？哪些不能一笔画成？ 　　经过尝试，你会发现，图8－2（a）、（c）、（e）是可以一笔画成的。而且图（c）、（e）可从任意一点出发，一笔画成回到出发点，而图（a）只能从A（或D）点出发，一笔画成到D（或A）点结束。 　　如果图形非常复杂，用这种逐一尝试的方法，则所花的时间较多，且有时还无法下结论。有没有一种简便的判断方法呢？下面就来研究这个问题。 　　上面研究的图形都是由点和线段（或弧）组成的，在数学中叫做图。图形中的点叫图的结点，线段（或弧）叫做图的边。作为一个图，其图形还必须满足以下条件： 　　（1）每条边都有两个端点（可以重合）作为结点； 　　（2）各条边之间互不相交。 　　一个图完全由它的结点和边的个数以及它们相互连结的情况来确定，而与边的曲直长短无关。 　　图中与一个结点相连结的边的条数称为这个结点的度数。度数为偶数的结点叫做偶结点。例如，图8－3中结点C、D、E都是偶结点。度数为奇数的结点叫做奇结点。例如，图8－3中结点A、B、F、G都是奇结点。 　　任何两点间都有线连接的图称作连通图。（如图8－3中D与G可通过DB、BA、AG连接） 　　观察例1中的五个图，其结点的奇偶性可列成下表： 　　从表中可以发现，一个图能否一笔画成，与图的奇结点的个数有密切联系，人们总结出如下规律： 　　一个图若是一笔画必定是个连通图。 　　一个连通图，若没有奇结点（即全是偶结点），那么这个图一定可以一笔画成，而且可以从任一偶结点出发，一笔画成回到出发点。 　　一个连通图，若只有两个奇结点，那么这个图也可以一笔画成。而且只能从某一奇结点出发一笔画成，到另一奇结点结束。 　　一个图，若奇结点个数多于两个，那么这个图就不能一笔画成。 例2 判断下列各图是否能一笔画出来。 解：其中（b）、（d）、（e）三个图无奇结点，所以可从任一点出发，一笔画成，并且回到出发点；（a）、（f）两图各有两个奇结点，所以可从其中一个奇结点出发，一笔画成，到另一个奇结点结束；而图（C）的八个结点都是奇结点，所以不能一笔画出来。 　　当作练习，请把例2中能够一笔画的图一笔画出来。 二、七桥问题和欧拉定理 问题2 七桥问题。 　　关于一笔画，曾有一个颇为著名的哥尼斯堡七桥问题。事情发生在18世纪的哥尼斯堡，有一条河流从这个城市穿过，河中有两个小岛A、B，河上有七座桥连结两个小岛及河的两岸（参看图8－5），那里的居民在星期日有散步的习惯。有的人想，能不能一次走遍七座桥，每座桥只走过一次，最后回到出发点？这个问题似乎不难，谁都想试一试，但谁也没有找到答案。后来有人写信请教著名的瑞士数学家欧拉。欧拉的头脑比较冷静，千百人的失败使他猜想：也许那样的走法根本就不存在。1936年他证明了自己的猜想。 　　欧拉解决七桥问题的方法独特，思想新颖，非常富有启发性。他用点表示小岛和两岸，用连结两点的线段表示连结相应两地的桥，得到由七条线段连结四个点而成的图形（参看图8－5（b））。这样七桥问题就变成了一个一笔画问题：能不能一笔画出这个图形，并且最后返回起点？前面我们虽然通过对例1的分析归纳出了一个连通图是否能一笔画出来的三条结论，但并没有证明，没有说明这是为什么。下面我们简要说明其中的道理。 　　一个连通图能否一笔画成主要是与结点的边数（也称度数）有关。假定某个图能一笔画成，如果结点P不是起点或终点，而是中间点，那么P一定是个偶结点。因为无论何时通过一条边进入P，由于不能重复，必须从另一条边离开P，因此与P连结的边一定成对出现，所以P是偶结点。如果一个结点Q是奇结点，那么在一笔画中只能是起点或终点。由此可以看出，在一个一笔画中，奇结点个数至多只能有两个。 　　由于哥尼斯堡七桥问题相应的图中有四个奇结点，所以不能一笔画成。也就是说，七桥问题无解，证实了欧拉的猜想。 　　欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的上述有关一笔画的三条结论，人们通常称之为欧拉定理。1736年，欧拉在圣彼得堡科学院作了一次报告，公布了他关于七桥问题的研究成果。欧拉在研究中提出了一种新颖的数学问题及思想方法，它标志着一门崭新的数学学科——图论的诞生。 　　对于一个连通图，通常把从某结点出发一笔画成所经