王伟业 路宇 李晓寒

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

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

一、问题描述

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

二、问题求解

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

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

三、问题思考

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