gudachao的个人博客分享 http://blog.sciencenet.cn/u/gudachao

博文

欧拉关于科尼斯堡桥问题的论文

已有 611 次阅读 2021-7-7 07:25 |个人分类:图论|系统分类:科研笔记

欧拉的论文:

Solutio problematis ad geometriam situs pertinentis


欧拉的证明:

在1735年8月26日,欧拉(Euler)发表了一篇包含柯尼斯堡桥(the Konigsberg bridge)问题的论文。他既解决了这个具体的问题,也给出了任意数量的陆地和任意数量桥的一般解决方法。这篇叫《Solutio problematis ad geometriam situs pertinentis》的文章后来在1741年发表。欧拉的文章分为21个自然段,下面是欧拉发表的这篇文章的简化版本。

在文章的前两段,欧拉介绍了柯尼斯堡桥问题。在第一段,欧拉声称,他相信这个问题和几何有关,但是不是他同时代人所熟知的几何(包括测量和计算),而是一种新的几何,即莱布尼兹(Leibniz)指出的位置几何。在第二段,欧拉给读者展示了如何解决柯尼斯堡桥问题的工作。欧拉提供了关于这个问题的一副素描图,并给这七个桥分别命名为a、b、c、d、e、f、g。在这一段,欧拉声明了这个问题的一般问法,“Can one find out whether or not it is possible to cross each bridge exactly once?”

1.jpg

给出这个一般的提问之后,他尝试去解决这个问题。欧拉开始探索各种方法以求得一个解决方案。在第三段,欧拉告诉读者,为了解决这个具体问题,他本可以写下所有可能的路径,但是这个技术将会花费大量时间,而且,如果是一个有更多个桥和大陆的更大的图,这种方法就无效了。因为这个问题,欧拉决定用一个不同的方法来解决这个问题。

 

在第四段,他开始发明了一个方便的系统来代表过桥简化了这个问题。欧拉决定使用小写字母代表桥,大写字母代表陆地。例如,图1中,AB代表从A陆地到B陆地的行程。进一步地,如果行程从陆地A到陆地B,然后又移动到陆地D,这可以简单地表示为ABD。在第五段,欧拉继续他的讨论,并解释道,在ABDC这个行程中,尽管有4个大写字母,但是只经过三座桥。欧拉解释道,无论有多少座桥,总会有比必要的桥多一个大写字母。因为这个原因,柯尼斯堡桥问题总共有七座桥,因此需要八个大写字母。

在第六段,欧拉继续解释他的方法的细节。他告诉读者,当从一个陆地到另一个陆地时候,如果两个陆地之间不止一座桥,不用在意从哪座桥走的。例如,有两座桥a和b,供行人从A到B,根据欧拉的注释,不用管从哪座桥上经过。在这一段,欧拉他正在处理的具体问题。他解释,使用他的原始图,柯尼斯堡桥问题实际需要八个大写字母,(A,B)对和(A,C)对必须依次出现两次,不用管哪一个字母先出现。而且,(A,D)对,(B,D)对,和(C,D)对必须一起出现在一条路径上,并且只出现一次。


在第七段,欧拉告诉读者,要么他需要找到满足问题的八个大写字母序列,要么他需要证明这种序列不存在。在他为柯尼斯堡桥问题这样做之前,他决定找到一个规律以发现是否存在一个路径,这个路径对一般性的问题有效。(注,就是找找看有没有一个普适性的规律)在第八段,他观察一个关于陆地和桥的更简单的例子。欧拉画了图2,并且他开始评估区域A被经过次数的情况。欧拉说,如果桥a被走过一次,区域A要么在起始点,要么在终点,并且只被使用过一次。如果桥a,b,c都被经过一次,区域A实际上使用了两次,无论A是起始点还是终点。类似地,如果有五座桥连到陆地A,A实际被经过3次。欧拉声称,“In general, if the number of bridges is any odd number, and if it is increased by one, then the number of occurrences of A is half of the result.”即,如果有奇数座桥连接A到别的大陆,桥的数量加一,然后除以二,就是路径中A必须经过的总次数。在这个过程中每座桥必须要经过一次,并且只经过一次。

在第九段,欧拉基于这个事实解决了柯尼斯堡桥问题。在这个例子中,因为有五座桥连到A,一定有三次经过A(见上图1),类似地,B,C,D一定会出现两次,因为它们都有3座桥连接。因此,3(A)+2(B)+2(C)+2(D)=9,但是欧拉已经声明过7座桥一定只经过8次区域。这就自相矛盾了!因此,在柯尼斯堡桥上有且仅走一次是不可能的。结束了,或者就这样?尽管柯尼斯堡的人也许对这个结果很开心,但是大数学家莱昂纳多欧拉(Leonhard Euler)并不满足于此。欧拉继续他的证明,来处理更多一般的情况。

 

欧拉的一般化

在第十段,欧拉继续他的讨论,如果条件变为所有的陆地都连接奇数个桥,每座桥有且仅走一次,能否走完,是可能给出结论的。欧拉说,如果每个大写字母必须出现的次数的总数超过总桥数1,这样的路程可以实现。然而,如果经过区域次数比桥的数量大1个,那么这个路程无法完成,就像柯尼斯堡桥问题一样。这是因为图二中欧拉利用奇数个球总结出的规律。这个规律对无论是两个或者更多的区块的一般性条件也成立。

在第十一和第十二段,欧拉处理的情况是一个连接了偶数个桥的区域。这种情况没有出现在柯尼斯堡桥问题中,因此一直被忽略直到现在。在一个具有区域X和偶数个桥的的情景中,会发生两种情况。第一种情况是,X是路程的起始点。在这种情况下,X将会出现两次,一次是起始点,一次是终点。在另一种情况下,X不是起始点。如果这种情况要发生,X将只经过一次,因为这个行程必将通过一个桥进入,又从另一个桥出来。类似地,如果X连接了四个桥,经过X的次数也是和X是否为起始点有关。如果行程从X开始,经过X的次数将是三次,但如果不是从X开始,经过X的次数将是2次。所以,一般来说,如果X有偶数个桥连接,那么,如果行程不是从X开始,经过X的次数将是桥数量的一半。如果行程是从X开始的,那么X出现的次数将是桥数量的一半再加1。

 

在第13到15段,欧拉解释了如果一个路径有且仅使用每个桥一次,如何来完成这个事情,并且还展现了自己的例子说明它如何有效工作。欧拉首先解释了他的简单的六步方法来解决任意具有陆地被河流分开并且河上面有桥跨过的的情况。第一步,欧拉把每块陆地指定为一个大写字母。第二步,他把计算出桥的总数,然后在这个总数上加一,把得到的数字写在他要画的表格上。第三步,他把大写字母列成一列,然后在大写字母后面写上桥连接的桥的数量。第四步,他用星号标出具有偶数座桥的陆地。第五步,在偶数座桥的陆地后面写上桥数量的一半,而在奇数座桥的陆地后面,写上桥数量的一半取整再加一。最后,欧拉把最后面一列的数加起来。如果这个总数比桥的总数加一小一或者相等,那么这个行程是可能的。需要指出的是,如果加起来的总数比桥总数加一小一,这个行程必须从标星号的陆地开始。如果,总数等于桥总数加一,行程必须从没标星号的区域开始。

 

例子

使用柯尼斯堡桥问题作为第一个例子,下面是欧拉展示的方法:

桥的数量=7,桥的数量加一=8

区域

桥数

区域要经过的次数

A

5

3

B

3

2

C

3

2

D

3

2

然而,3+2+2+2=9,这个数超过8,所以这个行程不可能。

 

因为这个例子相当本质,欧拉决定设计他自己的有两座岛、四条河和15个桥的情况。这种情况见图3。欧拉现在打算计算出是否有一条路径允许人经过每一条桥有且仅有一次。欧拉采用上面相同的步骤,即六个不同的陆地用六个大写字母表示,然后生成一个表格来核算是否可行,结果如下:

桥的数量=15,桥的数量加一=16

区域

桥数

区域要经过的次数

A*

8

4

B*

4

2

C*

4

2

D

3

2

E

5

3

F*

6

3

而且,4+2+2+2+3+3=16,等于桥数加一。这意味着行程可行。因为总数等于桥数加一,行程必须要么从D开始,要么从E开始。现在,欧拉已经知道行程可行,所要做的就是说明这个行程的具体路径是什么。欧拉选择了路径:EaFbBcFdAeFfCgAhCiDkAmEnApBoElD,这里他包含了两个陆地之间经过的桥。尽管这些信息是无关紧要的,因为对于一个已经知道行程是可能的行程确切的桥是无关紧要的,但是当要选择一个具体路径的时候它是有用的。这是一个很好的例子,展示了欧拉解决自然问题的方法。

 

欧拉的总结

在后面的几段,欧拉展示了另一种方法来计算对于一个给定的陆地区域、桥和河流,判断一个行程是否可行。在第16段,欧拉指出直接列在地块右侧的数字的总和是桥数量的两倍。这个事实后来被称为握手引理。一般地,握手引理说的是每座桥被数两次,一次是因为陆块经过桥所连接的另一个陆块。在第17段,欧拉继续陈述通向每个区域的桥的总数是偶数,因为这个数的一半等于桥的总数。然而,如果有奇数个陆块和奇数个桥这个行程就是不可能的。因此,欧拉证明了,如果有些陆块连接了奇数个桥,这些陆地块一定有偶数个。

 

然而,这还不足以证明当有一个路径,这个路径中每个桥有且仅用一次,正如科尼斯堡桥问题有偶数个陆块并有奇数座桥。因为这个原因,在第18和19段,欧拉增加了更多限制。欧拉解释道因为连接在各个陆块上的桥的数目总和等于实际桥数目总和的两倍(见握手引理)。所以,因此如果你在这个总数上加二再除以二,你就得到总桥数加一。这个数就和之前使用的一样,之前使用的这个数是用来辨别一个路径是否可能。如果所有的数都是偶数,那么表格中的第三列总和将会比总桥数加一少一。

 

欧拉然后解释道,我们显然可以得到下面这个结论:如果有两个陆块有奇数个桥,那么只要这个行程从其中一个有奇数个桥的区域开始,这个行程将总是可能的。这是因为如果偶数要减半,并且每个奇数要加一减半,这些的半数的总和将等于总桥数加一。然而,如果有四个或者更多陆地有奇数个桥,那么将不可能有这样的路径。这是因为所有奇数加一的半数的总数加上偶数半数的总数将会使第三列的总和大于总桥数量加一。因此,欧拉就证明了有至多两个有奇数个桥的的陆块。

 

因为这些说明,欧拉可以总结关于科尼斯堡桥问题更加一般的形式。在第二十段,欧拉给出了三条准则让人们用以判断每座桥有且仅使用一次的路径是否存在。第一,他宣称如果有超过两个陆块有奇数个桥,那么这种行程不可能存在。第二,如果有两个陆块有奇数个桥,只要行程从其中一个有奇数个桥的陆块开始,那么这个行程就是存在。第三,欧拉说如果没有有奇数个桥的陆块,那么行程从任一陆块开始都是可以完成的。陈述完这三个事实,欧拉在第21段总结了他的证明,这个证明简单地指出了,在发现一条路径存在之后,他们仍然必须努力写出一条有效的路径。欧拉相信,完成这个的方法是不重要的,并且他不想花大量时间在这上面。然而,欧拉确实建议关注如何从一个陆块到另一个陆块,而不是一开始就关注具体的桥梁。

 

欧拉的证明之所以出名,并不是因为他的证明,而是在证明过程中用到的抽象方法,用小写字母代替桥,用大写字母代替陆块。

以上翻译自维基百科

https://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem




http://wap.sciencenet.cn/blog-2356415-1294386.html


1 李宏翰

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-11-29 08:32

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部