哥尼斯堡七桥问题与一笔画

七桥问题与一笔画的通解（论文拟稿）在柯尼斯堡的一个公园里，有七座桥将一条河上的两座岛和两岸相连接。

当时有人提出了这么一个问题：如何一次性不重复不遗漏走完七座桥。

后来，数学家欧拉将它变成了一个一笔画问题（如图）。

从欧拉的简化图来看，似乎我们无论如何，也不能一笔画完图形。

但是，这是为什么呢?在这个图中，有ABCD 4个点，有五条线汇聚到A点，三条线汇聚到B,C,D 点，我们可以把这种有奇数条线（3条及以上）汇聚的点称为奇点，作为对应，把有偶数条线（4条及以上）汇聚的点称为偶点。

那么，我们不难发现，在任意封闭图形中，奇点的个数一定是偶数。

因为一条线定连接两个点（或重合），若存在奇数个奇点，则此图形定不符合封闭图形定义。

从一个奇点来看，若要一笔画成，则此奇点定是起笔点或停笔点。

起笔点，停笔点只有两个，所以说，奇点为两个或没有奇点的封闭图形可以一笔画。

回来看七桥问题，图中有四个奇点，以任意两个作为起笔点和落笔点，则还有两个奇点无法连接。

故七桥问题无解。

从上面总结出以下结论：■⒈凡是由偶点组成的连通图，一定可以一笔画成。

画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。

■⒉凡是只有两个奇点的连通图(其余都为偶点)，一定可以一笔画成。

画时必须把一个奇点为起点，另一个奇点为终点。

■⒊其他情况的图都不能一笔画出。

(奇点数除以二便可算出此图需几笔画成。

)我们可以把得到的结论推广到所有一笔画解法存在问题，如汉字“田”，我们观察到，它有四个奇点，故不可以一笔画。

而汉字“日”，只有两个奇点，则可以一笔画。

早在1736年，欧拉在交给彼得堡科学院的《哥尼斯堡7座桥》的论文报告中，就阐述了这种方法，也为后来的数学新分支--拓扑学的建立奠定了基础。

从这里我们可以看出，伟大的创造一开始可能并不像我们想象的那么高深莫测，仔细观察生活，我们也会有了不起的发现。

七桥问题和一笔画18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。

如图1所示：河中的小岛A与河的左岸B、右岸C各有两座桥相连结，河中两支流间的陆地D与A、B、C各有一座桥相连结。

当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。

图 1 图 2七桥问题引起了著名数学家欧拉（17071783）的关注。

他把具体七桥布局化归为图2所示的简单图形，于是，七桥问题就变成一个一笔画问题：怎样才能从A、B、C、D中的某一点出发，一笔画出这个简单图形（即笔不离开纸，而且a、b、c、d、e、f、g各条线只画一次不准重复），并且最后返回起点？欧拉经过研究得出的结论是：图2是不能一笔画出的图形。

这就是说，七桥问题是无解的。

这个结论是如何产生呢？请看下面的分析。

如果我们从某点出发，一笔画出了某个图形，到某一点终止，那么除起点和终点外，画笔每经过一个点一次，总有画进该点的一条线和画出该点的一条线，因此就有两条线与该点相连结。

如果画笔经过一个n次，那么就有2n条线与该点相连结。

因此，这个图形中除起点与终点外的各点，都与偶数条线相连。

如果起点和终点重合，那么这个点也与偶数条线相连；如果起点和终点是不同的两个点，那么这两个点部是与奇数条线相连的点。

综上所述，一笔画出的图形中的各点或者都是与偶数条线相连的点，或者其中只有两个点与奇数条线相连。

图2中的A点与5条线相连结，B、C、D各点各与3条线相连结，图中有4个与奇数条线相连的点，所以不论是否要求起点与终点重合，都不能一笔画出这个图形。

1736年，欧拉在圣彼得堡科学院作了一次学术报告。

在报告中，他证明了上述结论。

后来他又给出了鉴别任一图形能否一笔画出的准则，即欧拉定理。

为了介绍这个定理，我们先来看下面的预备知识：由有限条线组成的图形叫做网络，其中每条线都要求有两个不同的端点。

世界数学困难——一笔画[最新] 世界数学难题——哥尼斯堡七桥问题18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥。

将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题:一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点,大家都试图找出问题的答案，但是谁也解决不了这个问题。

这就是哥尼斯堡七桥问题，一个著名的图论问题。

1727年在欧拉20岁的时候，被俄国请去在圣彼得堡(原列宁格勒)的科学院做研究。

他的德国朋友告诉了他这个曾经令许多人困惑的问题。

欧拉并没有跑到哥尼斯堡去走走。

他把这个难题化成了这样的问题来看:把二岸和小岛缩成一点，桥化为边，于是“七桥问题”就等价于下图中所画图形的一笔画问题了，这个图如果能够一笔画成的话，对应的“七桥问题”也就解决了。

经过研究，欧拉发现了一笔画的规律。

他认为，能一笔画的图形必须是连通图。

连通图就是指一个图形各部分总是有边相连的，这道题中的图就是连通图。

但是，不是所有的连通图都可以一笔画的。

能否一笔画是由图的奇、偶点的数目来决定的。

那么什么叫奇、偶点呢,与奇数(单数)条边相连的点叫做奇点;与偶数(双数)条边相连的点叫做偶点。

如下图中的?、?为奇点，?、?为偶点。

1(凡是由偶点组成的连通图，一定可以一笔画成。

画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。

例如下图都是偶点，画的线路可以是:?????????????????2(凡是只有两个奇点的连通图(其余都为偶点)，一定可以一笔画成。

画时必须把一个奇点为起点，另一个奇点终点。

例如下图的线路是:?????????3(其他情况的图都不能一笔画出。

一笔画哥尼斯堡七桥问题1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支—-图论与几何拓扑.也由此展开了数学史上的新进程.问题提出后,很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。

七桥问题和欧拉定理。

欧拉通过对七桥问题的研究,不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。

故事背景七桥问题18世纪著名古典数学问题之一。

在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来（如图）。

问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次,再回到起点？欧拉于1736年研究并解决了此问题,他把问题归结为如下右图的“一笔画"问题，证明上述走法是不可能的.有关图论研究的热点问题。

18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来.当地居民热衷于一个难题:是否存在一条路线,可不重复地走遍七座桥。

这就是柯尼斯堡七桥问题。

欧拉用点表示岛和陆地,两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。

他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。

当Euler在1736年访问Konigsberg, Prussia（now Kaliningrad Russia）时，他发现当地的市民正从事一项非常有趣的消遣活动。

Konigsberg城中有一条名叫Pregel的河流横经其中,这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步,每座桥只能经过一次而且起点与终点必须是同一地点.Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。

著名数学家欧拉后来推论出此种走法是不可能的。