文档库

最新最全的文档下载
当前位置:文档库 > 9.一笔画和多笔画

9.一笔画和多笔画

第九讲一笔画和多笔画

问题1你能一笔画出一个“田”字吗?所谓一笔画出的意思就是在一张纸上(不允许折叠)笔不离纸,而且每一笔划(或称线段)只能画一次,不准重复。对于“串”字或“品”字呢?结果会怎样?(参看图8-1)

9.一笔画和多笔画

通过各种尝试发现,“田”字总也不能一笔画成,而“串”字却可以一笔画成。由于“品”字中的三个“口”字不连在一起,显然也不能一笔画成。

我们把那些能一笔画成的图形叫一笔画。一笔画问题主要讨论什么样的图形可以一笔画成。

例1下列图形哪些能一笔画成?哪些不能一笔画成?

9.一笔画和多笔画

经过尝试,你会发现,图8-2(a)、(c)、(e)是可以一笔画成的。而且图(c)、(e)可从任意一点出发,一笔画成回到出发点,而图(a)只能从A(或D)点出发,一笔画成到D(或A)点结束。

如果图形非常复杂,用这种逐一尝试的方法,则所花的时间较多,且有时还无法下结论。有没有一种简便的判断方法呢?下面就来研究这个问题。

上面研究的图形都是由点和线段(或弧)组成的,在数学中叫做图。图形中的点叫图的结点,线段(或弧)叫做图的边。作为一个图,其图形还必须满足以下条件:

9.一笔画和多笔画

(1)每条边都有两个端点(可以重合)作为结点;

(2)各条边之间互不相交。

一个图完全由它的结点和边的个数以及它们相互连结的情况来确定,而与边的曲直长短无关。

图中与一个结点相连结的边的条数称为这个结点的度数。度数为偶数的结点叫做偶结点。例如,图8-3中结点C、D、E都是偶结点。度数为奇数的结点叫做奇结点。例如,图8-3中结点A、B、F、G都是奇结点。

任何两点间都有线连接的图称作连通图。(如图8-3中D与G可通过DB、BA、AG连接)

观察例1中的五个图,其结点的奇偶性可列成下表:

9.一笔画和多笔画

从表中可以发现,一个图能否一笔画成,与图的奇结点的个数有密切联系,人们总结出如下规律:

一个图若是一笔画必定是个连通图。

一个连通图,若没有奇结点(即全是偶结点),那么这个图一定可以一笔画成,而且可以从任一偶结点出发,一笔画成回到出发点。

一个连通图,若只有两个奇结点,那么这个图也可以一笔画成。而且只能从某一奇结点出发一笔画成,到另一奇结点结束。

一个图,若奇结点个数多于两个,那么这个图就不能一笔画成。

例2 判断下列各图是否能一笔画出来。

9.一笔画和多笔画

解:其中(b)、(d)、(e)三个图无奇结点,所以可从任一点出发,一笔画成,并且回到出发点;(a)、(f)两图各有两个奇结点,所以可从其中一个奇结点出发,一笔画成,到另一个奇结点结束;而图(C)的八个结点都是奇结点,所以不能一笔画出来。

当作练习,请把例2中能够一笔画的图一笔画出来。

二、七桥问题和欧拉定理

问题2 七桥问题。

关于一笔画,曾有一个颇为著名的哥尼斯堡七桥问题。事情发生在18世纪的哥尼斯堡,有一条河流从这个城市穿过,河中有两个小岛A、B,河上有七座桥连结两个小岛及河的两岸(参看图8-5),那里的居民在星期日有散步的习惯。有的人想,能不能一次走遍七座桥,每座桥只走过一次,最后回到出发点?这个问题似乎不难,谁都想试一试,但谁也没有找到答案。后来有人写信请教著

名的瑞士数学家欧拉。欧拉的头脑比较冷静,千百人的失败使他猜想:也许那样的走法根本就不存在。1936年他证明了自己的猜想。

9.一笔画和多笔画

欧拉解决七桥问题的方法独特,思想新颖,非常富有启发性。他用点表示小岛和两岸,用连结两点的线段表示连结相应两地的桥,得到由七条线段连结四个点而成的图形(参看图8-5(b))。这样七桥问题就变成了一个一笔画问题:能不能一笔画出这个图形,并且最后返回起点?前面我们虽然通过对例1的分析归纳出了一个连通图是否能一笔画出来的三条结论,但并没有证明,没有说明这是为什么。下面我们简要说明其中的道理。

一个连通图能否一笔画成主要是与结点的边数(也称度数)有关。假定某个图能一笔画成,如果结点P不是起点或终点,而是中间点,那么P一定是个偶结点。因为无论何时通过一条边进入P,由于不能重复,必须从另一条边离开P,因此与P连结的边一定成对出现,所以P是偶结点。如果一个结点Q是奇结点,那么在一笔画中只能是起点或终点。由此可以看出,在一个一笔画中,奇结点个数至多只能有两个。

由于哥尼斯堡七桥问题相应的图中有四个奇结点,所以不能一笔画成。也就是说,七桥问题无解,证实了欧拉的猜想。

欧拉通过对七桥问题的研究,不仅圆满地回答了哥尼斯堡居民提出的问题,而且得到并证明了更为广泛的上述有关一笔画的三条结论,人们通常称之为欧拉定理。1736年,欧拉在圣彼得堡科学院作了一次报告,公布了他关于七桥问题的研究成果。欧拉在研究中提出了一种新颖的数学问题及思想方法,它标志着一门崭新的数学学科——图论的诞生。

对于一个连通图,通常把从某结点出发一笔画成所经过的路线叫做欧拉路。

例如,图8-6(a)中的图无奇结点,可以从A点出发,一笔画成回到A点,其路线为A→D→E→H→D→G→H→I→F→E→B→F→C→B→A。图8-6(b)中的图有两个奇结点C和E,可以从E出发一笔画成,到C结束。其路线为E→D→C →B→A→C。这两条路线都是欧拉路。应当注意:一个图如果存在欧拉路,那么不一定是唯一的。

9.一笔画和多笔画

人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。例如,图8-6(a)所表示的路线就是一条欧拉回路,因此相应的图就是一个欧拉图。

例3 图8-7是一公园的平面图,线段表示路径,要使游客走遍每条路且不重复,问出入口应设在哪里?

9.一笔画和多笔画

分析与解:这个问题实质上是一个一笔画问题。图中只有两个奇结点C和E,因此,只要把出入口分别设在这两个奇结点处,游客就能由入口进入公园,不重复地走遍每条路,然后从出口处离开公园。

例4 能否一笔画出一条曲线,使它和图8-8中的八条线段都只相交一次(不准在端点处相交)?

9.一笔画和多笔画

分析与解:尝试几次后,会感到很难下结论。事实上,直接寻找答案并不容易。我们可从七桥问题得到启示。原图形把平面分成了五个部分,分别用A、B、C、D、E五个点表示。两个点之间的连线正好用来表示与相应的线段相交一次,如图8-8(b)。于是,问题就变成了图8-8(b)中所表示的图能否一笔画成。因为图中A、B、C、D都是奇结点,因此,它不能一笔画成,即不存在符合题目要求的曲线。

例5图8-9表示一个展览馆的平面图,其中共有五个展览室,每个展览室都有一个门通向室外。能否设计一条参观路线,一次不重复地穿过每一个门并能回到原地。

9.一笔画和多笔画

分析与解:如果用A、B、C、D、E表示展览室,用F表示室外,用连线表示相应的门,那么图8-9(a)就变成了图8-9(b)于是问题就转化为判断图8-9(b)是否为欧拉图。

由图中可以看出,点C、D、E、F都是奇给点,因而图8-9(b)不具有欧拉回路。所以不是欧拉图。也就是说,不存在题中所要求的那种参观路线。

可以进一步考虑,关闭了哪两个门之后,就能设计出符合题中要求的参观路线了?为此,只要使图8-9(b)变为欧拉图,即使它的奇结点个数为O即可。例如抹去线段CD和EF后的图就没有奇结点了。也就是说,如果关闭C、D之间和E、F之间的两个门,就能设计出一条参观路线,一次不重复的穿过每一个门,并能回到原地。请你试一试,同时想一想,是否还存在其它的答案,一共有几种?

三、多笔画

在第一册第八讲例1中,我们讨论了下列图形的一笔画问题。

9.一笔画和多笔画

通过观察列出了下表:

9.一笔画和多笔画

由此表我们发现,一个图能否一笔画成与图的奇结点的个数有关系。如果我们再进一步观察,还可发现,这些图中的奇结点的数目都是偶数。这是一种偶然的巧合还是一种普遍的规律呢?如果我们再观察一些其它的图,结果也是没有出现奇结点数目是奇数的现象。于是我们可以作如下猜想:

在任何一个图中,奇结点的个数一定是偶数。

这是因为一个图的每条边都与两个结点相连结,所以,如果把一个图的所有结点的度数相加,由于每条边都计算了两次,其度数和是边数的2倍,它是偶数,可设为2n。又因为每个偶结点的度数都是偶数,它们的度数和当然是偶数,可设为2m。由此可知,所有奇结点的度数和为

2n-2m=2(n-m)(n、m为自然数)

也是一个偶数,但每个奇结点的度数都是奇数,所以奇结点的个数一定是偶数。否则,如果奇结点的个数是奇数,那么,因为奇数个奇数的和是奇数,就得到所有奇结点度数的和是奇数。这与上述结论相矛盾。这就说明,在任何一个图中,奇结点的个数一定是偶数。

例1 先数一数下列各图形中奇结点的个数。如果有的图形不能一笔画成,那么,至少几笔才能画成?

9.一笔画和多笔画

分析与解:图8-2(a)中只有两个奇结点,根据欧拉定理,可从A点出发一笔画出到B点结束,图(b)中有四个奇结点,不能一笔画成。图8-2(b)与图(a)比较,多出了折线CEFD。如果先一笔画出图(a),再添一笔画出折线CEFD,就可得到图(b)。因此,图(b)至少两笔才能画成。图8-2(c)中共有六个奇结点,也不能一笔画成。图(c)与图(b)比较又多出了一面旗子。它也含有两个奇结点,于是在两笔画出图(b)的基础上,再添一笔画上旗子,就成了图(c)。因此,图(c)至少三笔才能画成。

例2 图8-3(a)表示一所房子,问至少几笔才能画成?

9.一笔画和多笔画

分析与解:1图8-3(a)所示的图中共有B、E、F、G、I、J六个奇结点,所以不能一笔画成。如果我们将两个奇结点间的连线去掉一条,那么这两个奇结点就成为偶结点了。当我们把图中奇结点的个数减少到2个时,(想一想,奇结点个数为何不需减少到零个?)新的图就可以一笔画成了。

在图(a)中,第一笔画BJ,第二笔画GF。这样剩下I、E两个奇结点,如图(b)所示,这个图是可以一笔画成的。所以这所房子至少要三笔才能画成。

由上述两个例题看到,如果图中有两个奇结点,一笔就能画出;有四个奇结点,至少两笔才能画出;有六个奇结点,至少三笔才能画出;如果图中有八个奇结点,利用同样的道理分析,至少四笔才能画成。一般地,一个连通图如果有2n(n为自然数)个奇结点,那么至少画n笔才能画成。我们把这类问题称作多笔画问题。

四、邮递路线

问题一个邮递员每次送信,要走遍他负责投递的范围内的街道,完成任务后回到邮局。问他按怎样的路线走,所走的路程最短?

这个问题叫做最短邮递路线问题,是一个即有趣又实用的问题。

例3 图8-4(a)、(b)都表示街道图。图中A是邮局的位置,问邮递员应如何设计他的邮递路线,才能使他所走的路程最短?

9.一笔画和多笔画

分析与解:由于(a)所表示的图无奇结点,所以是一个欧拉图。他可以从邮局出发,不重复地走遍每条街道,回到邮局,这就是投递员的最短路线。而(b)所表示的图有六个奇结点,它不是一笔画,要不重复地走遍街道是不可能的。为了走遍所有的街道,必须重复走某些街道。重复走哪些街道才能使总路程最短呢?

由于任何一个图中奇结点的个数都是偶数,所以可把奇结点两两配对。如果在一对奇结点之间连一条虚线当作增添的重复边,奇结点就变成了偶结点,用这种方法可使原来的图变成没有奇结点的欧拉图(增添了重复边)。现在的问题是如何去连这些虚线,才能保证总路程最短。其原则是:

(1)连线(虚线)不能有重叠线段;

(2)在每一个圈上,连线长度之和不能超过圈长的一半。

9.一笔画和多笔画

例如,图8-5(a)中,连虚线时在KG一段上发生重叠。根据原则(1),应去掉重叠部分改成图8-5(b)。但在(b)中,对于BKJCB这个圈来说,增添的虚线长超过圈长的一半。根据原则(2),可以继续改进成(c)中增添虚线的情形,这是一种最好的增添虚线的方法。因此,最好的投递路线是ABCDE-FIFJCBKGFGHNA(参看图8-6)

9.一笔画和多笔画

例4 图8-7表示某城市的街道图,九个区都是边长为1公里的正方形,现需设一牛奶站,希望找一最佳地址,要能使送奶车以最短路程跑遍城市的所有街道,然后返回奶站。如果小明把奶站选在P点,试问他选的地方对吗?送一遍奶所走的最短路程比该城市全部街道的总长长多少?

9.一笔画和多笔画

分析与解:由于图8-7中有8个奇结点,所以必须重复走某些街道,才能送遍全城回到奶站。根据例3中的两条原则,重复路线可添设如图8-8。这样图中的结点全部为偶结点,说明奶站设在街道任何一处都一样。因此,小明选在P 点没有错。一次送遍全城回到奶站的最短路程应是24+4=28(公里)比城市全部街道总长多4公里,多走城市街道总长的16.7%。

习题十六

1.判断下列各图能否一笔画成。若不是一笔画,则至少几笔才能画成?

9.一笔画和多笔画

2.各单位在图中用数字标出,彼此间有路相通。一邮递员从邮局出发,向各单位传递邮件,他能否不走重复路线,也不经重复单位,又回到邮局?

3.一个邮递员投递信件的街道如图所示。图上数字表示各段街道的公里数。他从邮局出发,要走遍各街道,最后回到邮局,请为他设计一条最合理的路线,全程要走多少公里?

9.一笔画和多笔画

4.一个投递员投递的街区如图所示。图上数字表示各街道的长度。他从邮局出发,走遍各街道,最后回到邮局。请为他设计一条最优投递路线,并求出全程的公里数。

9.一笔画和多笔画

参考答案:

1.(a)有两个奇结点,可以一笔画成;(b)有8个奇结点,需四笔画成;(c)有4个奇结点,需两笔画成;(e)有10个奇结点,需五笔画成;(d)、(f)没有奇结点,是欧拉图,可以一笔画成回到起点。

2.能。路线可以这样设计:邮局→21→17→18→12→11→6→5→2→1→4→3→8→7→13→14→19→20→15→9→10→16→邮局

3.全程要走46公里,邮递路线如下图。

9.一笔画和多笔画

4.需要重复走的路段为FG、BC、DI和JNM。最佳路线为:邮局→F→A→B →G→F→G→H→C→B→C→D→I→D→E→J→H→M→N→J→N→M→邮局,全程要走33公里。