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

欧拉是如何将这生活的趣味问题转化为数学问题的呢?又是如何证明要想一次走过这七座桥是不可能的呢?

欧拉的方法十分巧妙:他用点A、B、C、D表示哥尼斯堡城的四个地区C (岛区)、B (北区)、D (东区)、A (南区);七座桥看成这四个点的连线,用1, 2, 3, 4, 5, 6, 7七个数字表示,如上图。

这样“七桥问题”就转化为是否能用一笔不重复地画出下图。

假设可以画出来,则图形中必有一个起点和一个终点,如果这两个点不重合,则与起点或终点相交的线都必是奇数条(称奇点),如果起点与终点重合,则与之相交的线必是偶数条(称偶点),而除了起点与终点外的点也必是“偶点”(里面的原因请读者想一想)。

若一个图形可以一笔画岀来,须满足如下两个条件:

(1) 图形必须是连通的(图中的任一点通过一些线一定能到达其他任意一点)。

(2) 图中的“奇点”数只能是0或2, 我们也可依此来检验图形是否可一笔画出。

回头来看看“七桥问题”,图中的4个点全都是“奇点”,因此不能一笔画岀,即,不可能不重复地走过七座桥。

欧拉并未轻视这个生活中的小问题。经过一年的研究,29岁的欧拉于1736年向彼得堡科学院递交了一份题为《哥尼斯堡的七座桥》的论文,不仅圆满地解决了这一问题,同时还开创了数学的一个新分支——图论。

(0)

相关推荐