一笔画及多笔画深入分析.doc

一笔画及多笔画深入分析

先讲一笔画概念：
-------------------我是分割线-----------------------
一． 扩展阅读部分：哥尼斯堡城七桥问题
18世纪初普鲁士的哥尼斯堡有一个公园，公园里有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来 (如图1)。

当地的市民经常从事一项非常有趣的消遣活动。这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。
很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。而利用普通数学知识，每座桥均走一次，那这七座桥所有的走法一共有7×6×5×4×3×2×1=5040种，而这么多情况，要一一试验，这将会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？因而形成了著名的“哥尼斯堡七桥问题”。
1735年，哥尼斯堡的几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉，请他帮忙解决这一问题。欧拉在亲自观察了哥尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七桥问题是不是原本就无解呢？
欧拉以深邃的洞察力很快证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地和小岛看成a、b、c、d 4个点，7座桥表示成7条连接这4个点的线，如图2所示证明图二能否一笔画及怎么画的问题即可解决哥尼斯堡城七桥问题。

1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑。也由此展开了数学史上的新历程。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。
-------------------我是分割线-----------------------
二． 一笔画问题探讨
先说明几个定义：
奇结点：有奇数条边的点称为奇结点。
偶结点：有偶数条边的点称为偶结点。
例如图三中：

A有3条边，是奇结点；
B有3条边，是奇结点；
C有2条边，是偶结点；
D有2条边，是偶结点；
E有3条边，是奇结点；
F有3条边，是奇结点；
G有4条边，是偶结点；
这个图有4个奇结点，3个偶结点。
凡是能一笔画的图，我们称之为欧拉图。欧拉图有以下3个特点：
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；无论能否一笔画，联通图中只可能有偶数个奇结点。
现在一笔画的概念都讲完了，下面做一下，“日”、“田”、“串”、“目”这几个字形能不能一笔画，能一笔画的话该怎么画？哥尼斯堡城七桥问题答案是什么？
-------------------我是分割线-----------------------
三. 邮递员最短线路问题
邮递员投递信件的街道如图十二所示，图上数字表示各街道长度（单位：千米）。他从邮局出发，走遍整个街道，最后回到邮局，怎样走路程最短？要走多少千米？（邮局在Y点）

分析：
图中偶结点有A、E、F、Y共4个，奇结点有B、C、D、G、H、I共6个，超过2个奇结点，这个图不能一笔画完成，即要不重复地走遍街道是不可能的。为了走遍所有的街道，必须重复走某些街道。重复走哪些街道才能使总路程最短呢？
由于任何一个联通图中奇结点的个数都是偶数，所以可把奇结点两两配对。如果在一对奇结点之间连一条虚线当作增添的重复边，奇结点就变成了偶结点。因为只能从偶结点Y出发，所以只能增加虚线以改变B、C、D、G、H、I的边数，使所有的这6个奇结点都变为偶结点。用这种方法可使原来的图变成没有奇结点的欧拉图（增添了重复边）。现在的问题是如何去连这些虚线，才能保证总路程最短。
为总路程最短，增加虚线的原则是：
（1） 连线（虚线）不能有重叠线路，
（2） 一个奇结点最多增加一条线路；
（3） 先连接路径最短的奇结点；
（4） 根据（1）（2）（3）可得到推论：在每一个圈上，连线长度之和不能超过圈长的一半。
为理解这四条原则，我们看看以下错误范例，图十三：

增加虚线后，B、C、D、G、H、I这6个奇结点都变为偶结点。但BC之间有3条重叠线路，且结点B和C分别都增加了3条线段，导致路线变长。
再看错误范例图十四

增加虚线后，B、C、D、G、H、I这6个奇结点都变为偶结点。也没有重叠线路，但请看BCHI这个圈子，原来圈长3+3+2+2=10，新增连线BI和CH，增加的路径和为6，新增线路没有按照先连接路径最短的奇结点原则，导致新增路径大于原圈长的一半。
解：
图十二中点A、E、F、Y的边都为2条，是偶结点；B、C、D、G、H、I的边都为3条，是奇结点。图中共有4个偶结点和6个奇结点，奇结点大于2个，不能一笔画。因为Y点是起点和终点，且Y点是偶结点，所以必须在奇结点B、C、D、G、H、I增加重复且尽可能短的线路，将B、C、D、G、H、I变为偶结点，从而全图结点都为偶结点才可实现。图十五是所需的最短路径图：

最短路程为
AB+2×BC+CD+DE+EF+2×DG+CH+BI+AY+FG+GH+2×HI+IY=2×8+4×2+3×6=42(千米)
13