在18世纪,东普鲁士哥尼斯堡有一条大河,河中有两个小岛。全城被大河分割成四块陆地,河上架有七座桥,把四块陆地联系起来(如图)。当时许多市民都在思索一个问题:一个散步者能否从某一陆地出发,不重复地经过每座桥一次,最后回到原来的出发地。


七桥问题


这就是历史上有名的哥尼斯堡七桥问题。

这个问题似乎不难解决,所以吸引了许多人来尝试,但是日复一日谁也没有得出肯定的答案。于是有人便写信求教当时著名的数学家欧拉(1707~1783)。欧拉毕竟是数学家,他并没有去重复人们已失败了多次的试验,而是产生了一种直觉的猜想:人们千百次的失败,也许意味着这样的走法根本就不存在。于是欧拉把七桥问题进行了数学的抽象。用A、B、C、D四个点表示四块陆地,用两点间的一条线表示连接两块陆地之间的一座桥,就得到如下图所示的一个由四个点和七条线组成的图形。


七桥问题


于是,七桥问题就转化为一个抽象图形是否可以“一笔画”的问题。什么叫“一笔画”呢?那就是笔不准离开纸,一口气画成整个图形;且每一条线只许画一次,不得重复。这样的图形能不能一笔画呢?

1736年欧拉证明了,答案是否定的。

为什么呢?

因为除了起点和终点之外,我们把其余的点称为中间点。如果一个图可以一笔画的话,对于每一个中间点来说,当画笔沿某条线到达这一点时,必定要沿另一条线离开这点,并且进入这点几次,就要离开这点几次,一进一出,两两配对,所以从这点发出的线必然要是偶数条。因此,一个图形能否一笔画就有了一个判别规则:

一个可以一笔画的图形最多只能有两个点(起点和终点)与奇数条线相连。

再看抽象图形,图中的四个点都是与奇数条(三条或五条)线相连的,根据判别规则,是不能一笔画的,从而证明了七桥问题所要求的走法是不存在的。

曾经难倒许多人的七桥问题,经过欧拉这样转化,就像哥伦布竖鸡蛋一样,简单而圆满地解决了。