APP下载

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

2019-10-21王伟业路宇李晓寒

青年生活 2019年14期
关键词:欧拉

王伟业 路宇 李晓寒

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

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

一、问题描述

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

二、问题求解

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

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

三、问题思考

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

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

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

猜你喜欢

欧拉
欧拉定理的Python简单验证
数学之王
三十六个军官问题与欧拉方阵
对欧拉错排问题的探究
欧拉白猫
读读欧拉,他是所有人的老师
欧拉不等式一个新的加强
欧拉不等式的一个加强猜想的验证
认识欧拉
他是我们大家的老师