为什么说“七桥问题”开创了一个新
18世纪初,东普鲁士的一座古城——哥尼斯堡有一条布勒尔河,它有两条支流,在城中心汇成大河。河中间有个岛,河上有7座桥。由于风景好,环境安静,人们喜爱到这里来散步。时间长了,有人提出一则趣题:怎样才能不重复地走遍7座桥,回到原出发地呢?这就是历史上著名的“七桥问题”。 这个问题看上去很容易,却无人能解决。有人向瑞士数学家欧拉求教。欧拉用点表示陆地,用连接两个点的线表示桥,于是七桥问题就转化为能不能一笔画出的问题。很明显,在任何可以一笔画出的图中,中间经过的顶点总是一进一出,不能重复,所以与中间顶点连接的边数一定是偶数。 如果要起点与终点重合,那么与该点连接的边数也一定是偶数。没有一个点...全部
18世纪初,东普鲁士的一座古城——哥尼斯堡有一条布勒尔河,它有两条支流,在城中心汇成大河。河中间有个岛,河上有7座桥。由于风景好,环境安静,人们喜爱到这里来散步。时间长了,有人提出一则趣题:怎样才能不重复地走遍7座桥,回到原出发地呢?这就是历史上著名的“七桥问题”。
这个问题看上去很容易,却无人能解决。有人向瑞士数学家欧拉求教。欧拉用点表示陆地,用连接两个点的线表示桥,于是七桥问题就转化为能不能一笔画出的问题。很明显,在任何可以一笔画出的图中,中间经过的顶点总是一进一出,不能重复,所以与中间顶点连接的边数一定是偶数。
如果要起点与终点重合,那么与该点连接的边数也一定是偶数。没有一个点是连接着偶数条边的,所以七桥问题是无解的。这也正是前一篇我们已经讨论过的一笔画问题的结论,凡能一笔画成的图形,奇点的个数不能多于2个。
显然不符合这一条件。
欧拉在解决七桥问题的过程中,首次引入了图的概念。图是由若干个顶点与若干条连接顶点的边组成的图形。两个图只要它们的顶点数目相同,并且在顶点之间具有相同的连接关系,这两个图就被看成是相同的。
关于七桥问题的图,也可以画成图3那种样子,这对问题的解决没有任何妨碍。因此,在图中,顶点的位置以及边的长短、曲直是无关紧要的,而讨论边的夹角、图形的面积等等问题更是毫无意义。这与欧氏几何很不相同,为数学研究开创了一个新的领域。
后来,人们发现在不同的实际问题中,顶点和边可以被赋予不同的含义。尤其近几十年来,逐步形成了以研究图的理论及其应用为目的的一个新的数学领域——图论。
在图论中,将可以一笔画的且起点与终点重合的图称为“欧拉图”。
一个图成为欧拉图的充分必要条件是:该图是连通图,并且所有的顶点都是偶点。在1736年发表的关于七桥问题的论文中,欧拉给出了判别一个图是不是欧拉图的必要条件。这是图论中第一个重要的研究成果。
由于用图论方法解决问题形象、直观,所以图论方法在物理学、化学、生物学、计算机科学、运筹学、心理学、语言学、社会学等众多的自然科学和社会科学领域中都有广泛的应用。
如今已经举世公认,1736年是图论的诞生年,欧拉是图论的创始人,七桥问题开创了图论这个新的数学领域。收起