图论中七桥问题的算法与思考

王伟业 路宇 李晓寒

摘要：图论诞生于七桥问题。数学家欧拉提出并解决了七桥问题。七桥问题运用到的数学思想和解决问题的方法值得学习和借鉴。

关键词：图论 七桥问题 欧拉

一、问题描述

18世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分为北区、东区、南区和岛区四个区域，全城共有七座桥将四个城区连接起来。于是，有一个有趣的问题：一个人能否在一次步行中经过全部的七座桥后回到起点，且每座桥只经过一次。

二、问题求解

首先，把实际问题转化为数学模型，如下图，ABCD分别为城区和岛区，每条线代表一座桥，问题就转化为：求一条回路，每条边经过一次且仅此一次。

首先定义“度”的概念。假设有一条路线由A到B，则A的出度为1，B的入度为1。度为入度+出度。于是对于这个问题，求一条回路，每条边经过一次且仅此一次，则说明ABCD四个点，每个点的度都为偶数，且各点的入度和出度相等。而对于上图，各点的边数都为奇数次，而由各边仅经过一次可得各点的度都为奇数，故七橋问题无解。

三、问题思考

在18世纪初，科学发展水平还不高的时期，人们看到这个问题都会想要通过穷举法来找出一条符合要求的回路，而回路一共有成千上万条，通过穷举法找到回路或者说明这个问题无解显然不现实。欧拉作为一名数学家，看到这个问题之后，首先想到把岛看为一个点，把桥看成是一条线，这样就把实际的七桥问题抽象转化成了一张图，这种建模的思想十分值得我们学习。七桥问题也为后来图论这门学科的诞生奠定了基础。

在处理很多实际问题的时候，我们要养成建模的思维，把实际问题抽象成数学模型，然后运用理论知识，解决问题。在解决一个问题的时候，拥有一个创造性的思维，可以把问题大大简化，事半功倍。

牛顿说：“如果我看得更远一点的话，是因为我站在巨人的肩膀上。”在过去科学技术不发达的时代，没有很多文献资料可以参考，欧拉等人做出的贡献是开创性的，正是这些开创性的成就，才使得我们有机会站在巨人的肩膀上，做出更多的研究。现在图论这门学科已经发展出了拓扑图论、结构图论、几何图论、代数图论等各个分支，而这些高深的研究都起源于欧拉开创性的思想。放到现在，我们遇到问题，肯定会想到建模，但是当时，没有人能想到，而欧拉想到了，并解决了他，为后世图论研究奠定了基础。而现在科学技术的重大进步，缺少的可能就是那创造性的思维。所以说，遇到问题，不拘泥于一成不变的方法，换一种思想，更科学地思考，问题可能就迎刃而解了。