有趣的一笔画问题

一笔画问题一笔画问题第页有趣的一笔画问题一笔画问题的提出：一笔画是一个大问题，为了更好的解决这个问题，我们从生活提出一笔画问题。我们先看一个公路检查员的问题：他为了检查几个城市之间的若干公路，希望在这些城市和公路组成的公路系统中找出一条路线，使他能不重复地恰好通过每条公路一次，而经过每个城市的次数不限。这就是拓扑学中的数学问题。一笔画的含义如果用笔在纸上连续不断又不重复，一笔画成某种图形，这种图形就叫一笔画。下面的画能一笔画成，你也试着描一描，画一画吧！那么是不是所有的图形都能一笔画成呢？那我们就要一起学习一笔画的规律。其实一笔画是一个几何问题，一个图形由一笔构成叫一笔画。传统意义上的几何学是研究图形的形状大小等性质，而对于平面图形的一笔画与多笔画问题，通常的几何方法是无能为力的，因为一个图形能否一笔画，与图形的大小、形状和线段的长短等几何概念都没有关系，而是与图形中线段的数目及连接关系有关，我们可以随意地将图形拉伸、压缩或弯曲，甚至在保持端点不动的前提下，还可以将某些线段“搬家”，只要图形的整体结构不变，能否一笔画的性质也就不会改变。一笔画问题是一个简单的数学游戏，即平面上由曲线段构成的一个图形能不能一笔画成，使得在每条线段上都不重复？例如汉字‘日’和‘中’字都可以一笔画的，而‘田’和‘目’则不能。(在日本动画片一休中，是采用对折纸张的方法画出‘田’和‘目’的一笔画）也是可取之处。一笔画图形的规律和判别：著名的哥尼斯堡七桥问题实质上就是一个一笔画问题。欧拉最终证明了这个图形是不能一笔画成的，并在关于七桥问题的报告中得到了任一网络图能否一笔画的判别法则。欧拉认为，能一笔画的图形必须是连通图。连通图就是指一个图形各部分总是有边相连的．但是，不是所有的连通图都可以一笔画的。能否一笔画是由图的奇、偶点的数目来决定的。数学家欧拉找到一笔画的规律是：1．凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。2．凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。3．其他情况的图都不能一笔画出。（有偶数个奇点除以二便可算出此图需几笔画成）比如附图：（a）为（1）情况，因此可以一笔画成；（b）（c）（d）则没有符合以上两种情况，所以不能一笔画成。补充：相关名词的含义◎顶点与指数：设一个平面图形是由有限个点及有限条弧组成的，这些点称为图形的顶点，从任一顶点引出的该图形的弧的条数，称为这个顶点的指数。◎奇顶点：指数为奇数的顶点。◎偶顶点：指数为偶数的顶点1、欧拉图必须是连通图。连通就是说任意两个点之间可以找到一条直接连接或经由其它点连接它们的线。例如图三就是个联通图，以下图四，由⊿ABC和⊿DEF构成的一个图就不是联通图。图三：图三：2、都由偶结点组成的连通图，是欧拉图。3、无论是否有几个偶结点（也可以没有偶结点），只有两个奇结点的连通图，是欧拉图。对于1.很好理解，图不联通，肯定也就不能一笔画了。例如图四是怎么都无法一笔画的（2个三角形之间没有连接线，当然不联通啦，也就不能一笔画啦）。对于2.和3.我们通过以下几个图来理解：我们来看图五图五图五：图五是个欧拉图，图中仅有一个点A，A既是图的起点又是图的终点，对A来说它有两条边，A是个偶结点。看图六图六图六：图六是个欧拉图，图中有两个点，A和B，其中一个是起点，则另一个必是终点。A和B都是奇结点。看图七图七图七：图七是个欧拉图。我们现在只看C点，C有2条边，被途经1次。因为连线途经C点，对C点来说，有一进线则必有一出线（否则也就不是途经了），点C是个偶结点。在一笔画问题中，我们对于线段的长短以及线段是弯是直或是弧线并不关心，我们关注的是点与点之间是否有连线以及图形的连接构造。因此可以说，就一笔画问题，所有的图都是由最基本的图五、图六、图七所组合而成的。我们接着看图八图八也是一个欧拉图。还看C点，C不是起点也不是终点，C有4条边，被途经2次。在欧拉图中，只要不是起点或终点的点永远是有一进线则必有一出线，这个点无论被线路途经过多少次，它都是个偶结点，B点、C点、D点都不是起点或终点，且都是偶结点。接着看图九图九是个欧拉图。这次我们重点看B点，点B是起点（或者是终点），它有3条边，被途经1次，它是个奇结点。在欧拉图中，起点和终点不是同一个点的话，起点或终点无论是否另有线路途经，无论被途经过多少次，它都是个奇结点。接着看图十图十是个欧拉图。图中的点都是偶结点，如果我们把A作为起点，则A也是终点，其它点都被途经，其中D被途经2次。我们也可以把D点作为起点，则D点也是终点，被途经1次。对于全是偶结点的联通图，它肯定是个欧拉图，而且任何一点都可以作为起点一笔画。看图十一图十一不是一个欧拉图，该图共有4个奇结点。对于一个欧拉图来说，如果起点和终点不是同一个点的话，那么起点必然是个奇结点，终点也必然是个奇结点。一个图要想一笔画，不可能有一个起点和多个终点，也不可能有多个起点和一个终点，更不可能有多个起点和多个终点。所以，只含有两个奇结点，无论有无偶结点的联通图都是欧拉图，这个图的一笔画只能从奇结点开始。另外还有一个推论：因为如果起点和终点不是同一个点的话，则有一起点就必有另一终点，起点和终点成对出现，且只能是奇结点（即使这个起点或终点又被其它线路途经，途经过程不能改变该点的奇偶性，不明白可回头看看图九的B点），所以无论能否一笔画，联通图中的奇结点总是成对出现，即联通图中只可能有偶数个奇结点。不信你画个含3个奇结点的联通图试试？总结结论：1、能一笔画的图必须是联通图；2、全是偶结点的联通图能一笔画，而且可以从任何一个点画起；3、联通图中只含有2个奇结点的话，无论该图有无偶结点都可以一笔画，但只能从任一奇结点开始画起；4、联通图中奇结点有2个以上的话，不能一笔画；5、无论能否一笔画，联通图中只可能有偶数个奇结点。现在一笔画的概念都讲完了，下面做一下，“日”、“田”、“串”、“目”这几个字形能不能一笔画，能一笔画的话该怎么画？哥尼斯堡城七桥问题答案是什么？(二)请把七桥问题的图绘画下来(用˙表示小岛和河的左右两岸，分别是A及B和C及D，而连接各地的七条桥则用─线表示。)奇数点的总数：__________偶数点的总数：__________(三)想一想：究竟哥尼斯堡的居民能否不重复走完七条桥？我认为哥尼斯堡是可以/不可以一次过走完而不重复，因为__________________________________________________________________________________________________________________________________________________________________________________________________________________________。一笔画问题的练习：1、下面这些图形，哪个能一笔画？哪个不能笔画？（1）（2）（3）（4）（）（）（）（）2、下面的图能一笔画成吗？如果能，应怎样画？描一描。3、下面的图能一笔画成吗？如果能，应怎样画？描一描。4、下图是一个公园的道路平面图，要使游客走遍每条路而又不重复，出、人口应该设在哪里？有趣的一笔画下面的这些简笔画都是一笔画成的，你也来试试吧！描一描画一画象象狮子狮子 桃子桃子兔兔西瓜西瓜鲸鹅蜗牛樱桃香蕉描一描画一画鲸鹅蜗牛樱桃香蕉一笔画问题的实际应用：一笔画问题的应用1.一辆洒水车要给某城市的街道洒水，街道地图如下：你能否设计一条洒水车洒水的路线，使洒水车不重复地走过所有的街道，再回到出发点2、下图是一个公园的平面图，能不能使游人走遍每一条路不重复？入口和出口，又应设在哪儿？3、甲乙两个邮递员去送信，两人同时出发以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？4、邮递员最短线路问题邮递员投递信件的街道如图十二所示，图上数字表示各街道长度（单位：千米）。他从邮局出发，走遍整个街道，最后回到邮局，怎样走路程最短？要走多少千米？（邮局在Y点）一笔画问题揭示的意义：一笔画问题的成功解决，其中蕴含的数学思想和策略，仍有着重要而现实的教育意义。品味一笔画问题鼓励学生大胆猜想，提高抽象分析能力，重视符号处理技巧，培养数学建模能力，树立正确数学观念。解决“七桥问题”的困难之处何在呢？显然最困难之处在于把它简化成网络图。在欧拉之前解这道题的人之所以未能成功，主要在于他们或者没有想到要简化问题，或者作不出欧拉的网络图。不难看出，如果网络图已经有了，再来研究它能否一笔画，难度就小多了，相信在那批首先研究这个问题的人中，肯定有人能解决它。而现实的数学问题当然是类似“七桥问题”这种形式，而不是类似网络图这种形式。这就是说，解决现实的数学问题的第一步，通常也是最困难的一步，也就是如何将问题用数学语言和符号表示出来。这就是著名数学教育家弗赖登塔尔所强调的“数学化”。这就是一笔画问题解决所揭示的意义。（数学化:把一笔画问题数学化，以点表示城市，以弧表示公路，构成的网络图就表示某个简单公路系统。）一笔画问题规律的证明：先定义能一笔画出并回到起点的图为欧拉图，连通就是说任意两个节点之间可以找到一条连接它们的线。这个要求看来很重要，直观方法中与这一点对应的是说原图本身不能是分成多个的。证明：设G为一欧拉图，那么G显然是连通的。另一方面，由于G本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍，从而均为偶数。反之，设G连通，且每个顶点的度均为偶数，欲证G为一欧拉图。为此，对G的边数归纳。当m=1时，G必定为单结点的环，显然这时G为欧拉图。设边数少于m的连通图，在顶点度均为偶数时必为欧拉图，现考虑有m条边的图G。设想从G的任一点出发，沿着边构画，使笔不离开图且