9一笔画和多笔画.docx
《9一笔画和多笔画.docx》由会员分享,可在线阅读,更多相关《9一笔画和多笔画.docx(12页珍藏版)》请在冰点文库上搜索。
9一笔画和多笔画
9.一笔画和多笔画
第九讲一笔画和多笔画
问题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年,欧拉在圣彼得堡科学院作了一次报告,公布了他关于七桥问题的研究成果。
欧拉在研究中提出了一种新颖的数学问题及思想方法,它标志着一门崭新的数学学科——图论的诞生。
对于一个连通图,通常把从某结点出发一笔画成所经过的路线叫做欧拉路。
例如,图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。
这两条路线都是欧拉路。
应当注意:
一个图如果存在欧拉路,那么不一定是唯一的。
人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。
具有欧拉回路的图叫做欧拉图。
例如,图8-6(a)所表示的路线就是一条欧拉回路,因此相应的图就是一个欧拉图。
例3图8-7是一公园的平面图,线段表示路径,要使游客走遍每条路且不重复,问出入口应设在哪里?
分析与解:
这个问题实质上是一个一笔画问题。
图中只有两个奇结点C和E,因此,只要把出入口分别设在这两个奇结点处,游客就能由入口进入公园,不重复地走遍每条路,然后从出口处离开公园。
例4能否一笔画出一条曲线,使它和图8-8中的八条线段都只相交一次(不准在端点处相交)?
分析与解:
尝试几次后,会感到很难下结论。
事实上,直接寻找答案并不容易。
我们可从七桥问题得到启示。
原图形把平面分成了五个部分,分别用A、B、C、D、E五个点表示。
两个点之间的连线正好用来表示与相应的线段相交一次,如图8-8(b)。
于是,问题就变成了图8-8(b)中所表示的图能否一笔画成。
因为图中A、B、C、D都是奇结点,因此,它不能一笔画成,即不存在符合题目要求的曲线。
例5图8-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中,我们讨论了下列图形的一笔画问题。
通过观察列出了下表:
由此表我们发现,一个图能否一笔画成与图的奇结点的个数有关系。
如果我们再进一步观察,还可发现,这些图中的奇结点的数目都是偶数。
这是一种偶然的巧合还是一种普遍的规律呢?
如果我们再观察一些其它的图,结果也是没有出现奇结点数目是奇数的现象。
于是我们可以作如下猜想:
在任何一个图中,奇结点的个数一定是偶数。
这是因为一个图的每条边都与两个结点相连结,所以,如果把一个图的所有结点的度数相加,由于每条边都计算了两次,其度数和是边数的2倍,它是偶数,可设为2n。
又因为每个偶结点的度数都是偶数,它们的度数和当然是偶数,可设为2m。
由此可知,所有奇结点的度数和为
2n-2m=2(n-m)(n、m为自然数)
也是一个偶数,但每个奇结点的度数都是奇数,所以奇结点的个数一定是偶数。
否则,如果奇结点的个数是奇数,那么,因为奇数个奇数的和是奇数,就得到所有奇结点度数的和是奇数。
这与上述结论相矛盾。
这就说明,在任何一个图中,奇结点的个数一定是偶数。
例1先数一数下列各图形中奇结点的个数。
如果有的图形不能一笔画成,那么,至少几笔才能画成?
分析与解:
图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)表示一所房子,问至少几笔才能画成?
分析与解:
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是邮局的位置,问邮递员应如何设计他的邮递路线,才能使他所走的路程最短?
分析与解:
由于(a)所表示的图无奇结点,所以是一个欧拉图。
他可以从邮局出发,不重复地走遍每条街道,回到邮局,这就是投递员的最短路线。
而(b)所表示的图有六个奇结点,它不是一笔画,要不重复地走遍街道是不可能的。
为了走遍所有的街道,必须重复走某些街道。
重复走哪些街道才能使总路程最短呢?
由于任何一个图中奇结点的个数都是偶数,所以可把奇结点两两配对。
如果在一对奇结点之间连一条虚线当作增添的重复边,奇结点就变成了偶结点,用这种方法可使原来的图变成没有奇结点的欧拉图(增添了重复边)。
现在的问题是如何去连这些虚线,才能保证总路程最短。
其原则是:
(1)连线(虚线)不能有重叠线段;
(2)在每一个圈上,连线长度之和不能超过圈长的一半。
例如,图8-5(a)中,连虚线时在KG一段上发生重叠。
根据原则
(1),应去掉重叠部分改成图8-5(b)。
但在(b)中,对于BKJCB这个圈来说,增添的虚线长超过圈长的一半。
根据原则
(2),可以继续改进成(c)中增添虚线的情形,这是一种最好的增添虚线的方法。
因此,最好的投递路线是ABCDE-FIFJCBKGFGHNA(参看图8-6)
例4图8-7表示某城市的街道图,九个区都是边长为1公里的正方形,现需设一牛奶站,希望找一最佳地址,要能使送奶车以最短路程跑遍城市的所有街道,然后返回奶站。
如果小明把奶站选在P点,试问他选的地方对吗?
送一遍奶所走的最短路程比该城市全部街道的总长长多少?
分析与解:
由于图8-7中有8个奇结点,所以必须重复走某些街道,才能送遍全城回到奶站。
根据例3中的两条原则,重复路线可添设如图8-8。
这样图中的结点全部为偶结点,说明奶站设在街道任何一处都一样。
因此,小明选在P点没有错。
一次送遍全城回到奶站的最短路程应是24+4=28(公里)比城市全部街道总长多4公里,多走城市街道总长的16.7%。
习题十六
1.判断下列各图能否一笔画成。
若不是一笔画,则至少几笔才能画成?
2.各单位在图中用数字标出,彼此间有路相通。
一邮递员从邮局出发,向各单位传递邮件,他能否不走重复路线,也不经重复单位,又回到邮局?
3.一个邮递员投递信件的街道如图所示。
图上数字表示各段街道的公里数。
他从邮局出发,要走遍各街道,最后回到邮局,请为他设计一条最合理的路线,全程要走多少公里?
4.一个投递员投递的街区如图所示。
图上数字表示各街道的长度。
他从邮局出发,走遍各街道,最后回到邮局。
请为他设计一条最优投递路线,并求出全程的公里数。
参考答案:
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公里,邮递路线如下图。
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公里。