还剩4页未读,继续阅读
文本内容:
二十七一笔画图形 一笔画的理论是由大数学家欧拉(Euler)建立的.他在建立这一理论的过程中方法新颖、独特,使人们折服、倾倒.并且为人类思想宝库奉献了一颗耀眼的珍珠,这颗珍珠将在人类的智慧史上放射着不灭的光辉. 同学们,你肯定想知道什么是一笔画吧?让我们从一个游戏开始. 问题
27.1图27-1中有四个图形,你能一笔画出来吗? 这就是一笔画问题.对以上四个图,经过几次试画读者不难发现图
(1)可一笔画成且从任一点出发均可回到出发点;图
(2)可一笔画成但起点只能在D或B点且不能回到出发点;图
(3)、
(4)均不能一笔画成. 如果一个图形可以用笔不离纸且每条线都画到并不准重复,则这个图形就叫做一笔画图形. 关于一笔画问题有下面几个问题需要解决
(1)怎样简单地判断一个图形能否一笔画?
(2)如果能一笔画,什么时候可回到出发点,什么时候又不能?
(3)对不能回到起点的一笔画,应把何处作为起点?何处作为终点?
(4)若一个图形不能一笔画,那么至少需要几笔画成? 当图形较简单时(如图27-1),只要进行几次“试画”,就可以回答上述所有问题.但是,当图形较复杂时,要回答上述问题难度就大了. 同学们不信可以试试,如果你不看下文就能独立地解决这个问题,那么在这一问题上你就与大数学家欧拉一样聪明了. 下面我们开始研究一笔画问题. 让我们从产生这一问题的历史背景谈起吧!说起来还有一段引人入胜的故事呢! 事情发生在公元18世纪普鲁士的哥尼斯堡城.一条河从这个城市穿过,河中有两个小岛把主流分成了两半.河上有七座桥连接两岛同河的两岸沟通(如图27-2).这是个风景秀丽的地方,吸引了许多游人.人们在这里参观、散步.不知谁最先提出了一个问题一个散步者怎样能一次走遍这七座桥,最后又回到出发点,而每座桥只走过一次,不许重复. 这一问题似乎不难,谁都愿意试一试,但没有一个胜利者.这下引起了许多优秀人才极大的兴趣和好奇心. 过了很久一段时间,这件事被瑞士大数学家欧拉知道了.欧拉头脑比较冷静,千百人的失败,使欧拉猜想也许那样的走法根本不存在.经过艰辛的探索以后,他于1736年在圣彼得堡科学院作了一次报告,终于向人们解开了“七桥问题”之谜,并彻底地解决了一笔画的所有问题. 下面让我们来看看欧拉是怎么解决这一问题的,从而欣赏一下这位数学泰斗精彩绝妙的数学思维. 欧拉在对图形进行了深入细致的研究之后,发现任何图都是由点和线组成的.他把图中的点分成两类若从一点发出的线的整目是偶数,就称为一个偶点,若是奇数就称为奇点.如图27-3,除B、J、D、F是奇点外,其它均为偶点.欧拉认为,分开的图形显然是不能一笔画的[如图27-1
(4)].一个连在一起的图(叫连通图),能不能一笔画与此图形中奇点的个数有关. 欧拉先假定一个图形已经一笔画成,再考察其特点它一定有一个起点B,一个终点E和一些中间点mi(图27-4).
(1)首先可断言所有中间点mi必为偶点,因为每次有一条线画进mi必有一条从mi画出的线与之配对.
(2)如果B不与E重合,则B、E必为奇点.事实上,我们先从B画出去,即使中途画进B点,最后还是要画出去,所以画出B点的线总比画进来的线多一条,因而B是奇点.同样E也为奇点.
(3)如果B与E重合,则B(即E)必为偶点.这是因为进、出B点的线一样多. 反过来可以证明凡具备条件
(1)、
(2)、
(3)的图形均可一笔画. 由此欧拉就得到了下面的结论一笔画定理若一个连通图形奇点的个数为0或2时,其图形必为一笔画(反之亦然).而且
(1)当奇点个数为0时,可以取任一(偶)点为起点,最后仍回到这一点;
(2)当奇点个数为2时,必须以一个奇点为起点,另一个奇点为终点. 应特别注意欧拉解决这一问题时用的思维技巧是从结果入手考虑.人们称它为倒推法.问题
27.2图27-5中的几个图形是否可一笔画?解图
(1)中全为偶点.故可以一笔画. 图
(2)中有6个奇点,故不能一笔画. 图
(3)中有2个奇点,故可以一笔画. 到此,我们已圆满地回答了开始提出的问题
(1)、
(2)、
(3),关于问题
(4)有以下结论 多笔画定理有2n(n>1)个奇点的连通图形,可以用n笔画完(彼此无公共线),而且至少要n次画完.问题
27.3图
27.3图27-3和27-5
(2)分别要几笔画完? 理论的目的在于应用.和其它数学理论一样,一笔画是一种数学模型,要把它应用于实际,还必须学会把实际问题抽象、转化成这种模型.问题
27.4图
27.4图27-6是一个公园的平面图,要使游客走遍每条路且不重复,问出、入口应设在哪里?解本问题相当于一笔画问题. 由于图中有两个奇点,由一笔画定理,只要将出、入口分别设在D、I两点,游客就可以从入口进入公园,不重复地走遍所有小径,而最后从出口处离开公园.问题
27.5能否一笔画出一条线路,使它和图27-7的8条线段都相交且仅相交一次(并不在端点处相交)?分析本题的实质并不是研究图27-7本身的一笔画问题,而是研究图中虚线表达的图的一笔画问题.解图27-7中的8条实线段,把平面分成了5个部分,而把每个部分看成一个点,用
①、
②、
③、
④、
⑤ 因为虚线图有4个奇点(
①、
②、
③、
④),由多笔画定理,它至少得2笔画成. 注意本题的关键(题眼)是把5块区域看成5个点,从而把实际问题抽象成一笔画的问题. 下面我们再运用这种方法来解决著名的“七桥问题”.问题
27.6一个散步者能否一次走遍图27-8
(1) 所示的七座桥且不许重复?解河流把地平面分成四个区域A、B、C、D,把这四个区域看成四个点.每两块区域之间有一座桥相通就相当于在相应的两点之间连一条线段,这样我们就把七桥问题抽象成了图27-8
(2)的一笔画问题.因为本图有四个奇点,故原题中散步者的散步路线是不存在的.问题
27.7图27-9
(1)是某展览馆的平面图.每个房间都有一扇门通往馆外,每相邻两个房间之间各有一扇门相通.参观者能不能一次无重复地穿过每一扇门?如不能,关闭哪一扇门后就能无重复地穿过每一扇门了?并问出、入口在哪里?解
①~
⑥表示.把它们看成6个点,用一线段表示一扇门,就可得到图27-9
(2).此图有
③、
④、
⑤、
⑥4个奇点,所以不能一笔画成.即表明,参观者要想不重复地穿过每一扇门是不可能的. 第二问实际上是问在图
(2)中去掉哪一段线就能使图形一笔画出.由于
③、
④、
⑤、
⑥均为奇点,只要关闭
③、
④之间的一扇门,就只剩下
⑤、
⑥两个奇点了.这时,只要把
⑤、
⑥分别当做出、入口,参观者就可以不重复地一次穿过其余各门了. 同样地,从图中易看出,关闭
④、
⑤,或
⑤、
⑥,或
④、
⑥,或
③、
⑥之间的任一扇门,参观者也可以如愿以偿. 我们还可以证明在一个图中奇点的个数必定是偶数. 从本题的解法我们不难看到在两个奇点之间去掉一条连线,这两个奇点就同时变为偶点.同样,在两个奇点之间增加一条连线,也可使这两个奇点同时成为偶点.问题
27.8在奇点和偶点之间连一条线后,图中的奇、偶点个数有什么变化? 以上讲了许多一笔画知识,也许学过后一些肯动脑筋的同学可能会想一笔画知识除了做数学游戏外,还有什么实用价值呢?为了回答这个问题我们先介绍几个名词 对一个连通图,通常把从某点出发一笔画成所经过的路线叫做欧拉路;把一笔画成回到出发点的欧拉路叫欧拉回路;具有欧拉回路的图叫做欧拉图. 现在城市的街道及公园、展馆的参观路线,严格地说来大多数都设计得杂乱无章.人们上、下班,参观游览,邮递员送信及各种车辆行驶都要走许多重复的路,且会漏掉许多事物.这样不但消耗了许多不必要的财力,而且浪费了大量的时间. 同学们,你们学了一笔画知识后,就可以当未来世界的设计师,把未来的城市街道设计成某种欧拉回路,并把公园、展馆设计成欧拉路.到那时,投递员叔叔再送邮件时,就可一次跑完所有街道最后回到邮局;人们参观公园只需走一趟就会对所有内容一览无余.在你们的劳动下,世界将会变得更美好.。