欧拉七桥问题

  东普鲁士的哥尼斯堡城是一个风景宜人的旅游胜地,也是一个在战争中双方必争的战略要地。

  哥尼斯堡城中有一条河叫布勒格尔河,该河横贯城区。它有两条支流,分别称为新河和旧河,两条支流在城中心汇合,成为一条主流(大河)。在新旧两河合流处,中间有一个岛形地带,这是繁华的商业中心,这种分布情况,把全城分为北区、东区、南区及中央的岛区四个区域,这四个区域分别由七座桥相连,全市分布情况见图(1).关于哥尼斯堡城与这七座桥有不少传说,下面便是其中的一个。

 

  在一次战争期间,入侵部队要经过这个城市,为延阻入侵者的进攻,当地驻军派出一支工兵部队破坏这七座桥。他们设想用一辆装载炸药的卡车,每过一桥便炸毁该桥,因此卡车无法从原桥驶回。指挥员想设计一种卡车行驶路线的方案,要将七座桥都这样炸毁,不许遗漏一座桥。试问他们能办得到吗?

  我们把这个问题转化为数学问题:把东、南、北及岛四区看成四个点,连接它们的七座桥看成七条通路,如东区与北区由桥3相连,则它们之间有一条通路,南区与北区没有桥直接相连,则它们之间就没有直接的通路。以A代表岛区,BCD分别代表北、东、南三区,把这四个点和连接它们的代表七座桥的通路在图上画出来,就得到图(2)

 

  现在问题可以叙述为:以ABCD这四点中的任一点为起点,能否不重复地用一笔便将上面的图形画出来。

  当时,驻军的指挥官找不出这样的一种方法,所以只得采取其他的办法来完成任务。至于有没有这样的方法?如果没有,原因是什么?这些问题他们就无从回答了。

  这个问题被人们称为哥尼斯堡七桥问题。欧拉曾仔细研究过这个问题并完满地对它作了解答,由此开创出一门新的数学学科——图论。因此,后来人们又称此问题为欧拉七桥问题。

  欧拉思考这个问题的方法是这样的:

  一个图如果能够不重复地一笔画成,那么它必须有一个起点和一个终点。

  如果起点与终点是同一个点,那么从这点出发的路线条数与回来的路线条数是一样多的,而且这些通路又不能重复使用,因此与此点相连的通路有偶数条。同样,中间经过的点进去和出来的通路也应该是偶数条。具有这种性质的点,我们称为偶点。

  如果起点与终点不相同,按照上面的推理,知道连接这两个点的通路应该是奇数条。这样的点我们称为奇点。

  现在问题容易解决了。如果一个图能不重复地一笔画而成,那么它必须具有的奇点数或者是0,或者是2.这是因为中间点都是偶点,只有起点和终点才可能是奇点。现在我们来看看哥尼斯堡的图,可以发现它的四个顶点ABCD都是奇点,因此一笔画是不可能的。

  欧拉不愧为数学上的一个天才,他的思维如此巧妙,不能不令后人为之折服。

 

  上面实际上只解决了图的这类问题的一部分,另外还有一个问题:

  是不是奇点数为02的图就一定能一笔画成呢?结论是肯定的。这个结论的详细证明我们就不在此详述了。

  过去我们曾经发现,不少数学爱好者希望完成这样一个问题,就是不重复地一笔画画出如图(3)的图形。据出题者言,谁能一笔画出此图形,他将给以巨额奖励。许多同学为此耗费了不少的宝贵时间和精力。亲爱的朋友们,现在你根据上面所讲的知识,判断一下,这个图形能否一笔画成呢?

  有了这些基础知识,你可以画一些自己喜爱的图形来考考自己,也可以用来检测别人的智力。