
18世纪初普鲁士的哥尼斯堡,有一条河穿过,河上有两个小岛,有七座桥把两个岛与河岸联系起来(如右上图)。有个人提出一个问题:一个步行者怎样才能不重复、不遗漏地一次走完七座桥,最后回到出发点。
问题提出后,很多人对此很感兴趣,纷纷进行试验,但在相当长的时间里,始终未能解决。而利用普通数学知识,每座桥均走一次,那这七座桥所有的走法一共有5040种,而这么多情况,要一一试验,这将会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢?因而形成了著名的”哥尼斯堡七桥问题”。
后来大数学家欧拉把它转化成一个几何问题即一笔画问题,在经过一年的研究之后,29岁的欧拉提交了《哥尼斯堡七桥》的论文,圆满解决了这一问题。
他不仅解决了此问题,且给出了连通图可以一笔画的充要条件是:
奇点的数目不是0 个就是2 个
连到一点的数目如是奇数条,就称为奇点,如果是偶数条就称为偶点
那为什么奇点的数目不是0 个就是2 个呢?
我们可以想象一笔画成,其实就是从一点出发,又从另一点回归,然后形成闭合通路,我们知道,一个点它的功能只能是:起点、终点、通点。起点和终点可以单数线连接,而通点必定得是双数线连接(进和出)。
- 所以奇点个数为0,那么任意点可以作为起点并且该点也为回归点,这样就完成了一笔画成;
- 如果奇点个数为单数(虽然此情况不存在),必定只能出发而不能回归,因此不能一笔画成;
- 如果奇点个数为2,选择从奇点出发,从另一个奇点回归,同样也可以一笔画成;
所有的点中,除了作为起终点之外,剩下的功能就作为通点使用。
奇点个数(0除外)的一半就是画成该图形的最少笔数。
因此,使得一个图形可以一笔画,必须满足如下两个条件:
1.图形必须是连通的;2.图中的”奇点”个数是0或2。
答案是无解的,你要记住,七桥问题即:能否笔不离纸,不重复地一笔画完整个图形。“一笔画”问题,数学分析:一笔画有起点和终点,起点和终点重合的图形称为封闭图形,否则便称为开放图形。除起点和终点外,一笔画中间可能出现一些曲线的交点。只有当笔沿着一条弧线到达交点后,又能沿着另一条弧线离开,也就是交汇于这些点的弧线成双成对时,一笔画才能完成,这样的交点就称为“偶点”。如果交汇于这些点的弧线不是成双成对,也就是有奇数条,则一笔画就不能实现,这样的点又叫做“奇点”
结论:若是一个一笔画图形,要么只有两个奇点,也就是仅有起点和终点,这样一笔画成的图形是开放的;要么没有奇点,也就是终点和起点连接起来,这样一笔画成的图形是封闭的。由于七桥问题有四个奇点,所以要找到一条经过七座桥,但每座桥只走一次的路线是不可能的。