你听说过七桥问题吗？

1、哥尼斯堡七桥问题

哥尼斯堡曾是东普鲁士的首府，现称加里宁格勒，在俄罗斯境内。在第二次世界大战时，法军经这里入侵波兰。后来，苏军也是从此地打进德国的。所以哥尼斯堡是一座历史名城。同时，在这里诞生和培养过许多伟大人物。如著名唯心主义哲学家康德，终生没有离开此城。在哥尼斯堡城中有一条布勒格尔河，横贯城中，如图1。河有两条支流，一条称新河，条叫旧河，在城中心汇合成一条主流，在合流的地方，中间有座河心岛，这是城中繁华的商业中心。由于布勒格尔河的流过，使全城分成为四个地区：岛区、北区、东区和南区。在布勒格尔河上，架了七座桥，其中五座将河岛与河岸连接起来，另有两座架在二支流上。这一别致的桥群，吸引了众多的哥尼斯堡居民和游人来此河边散步或去岛上买东西。

图1

早在18世纪，就有人提出这样的问题：“能否在一次散步中每座桥都走一次，而且只能走一次，最后又回到原来的出发点？”这个问题吸引了不少人去思考实验。事实上，要走遍这七座桥的所有走法共有=7！=5040种，要想一一试验过，谈何容易。是否在这5040种走法中存在着一条走遍七座桥而又不重复的路线呢？谁也回答不了。因而形成了著名的“哥尼斯堡七桥问题”。

1735年，有几名大学生写信给当时正在俄国彼得堡科学院任职的天才数学家欧拉，请他帮助解决。欧拉并未轻视生活小题，他似乎看到其中隐藏着某种新的数学方法。经过一年的研究，29岁的欧拉于1736年向彼得堡科学院递交了一份题为《哥尼斯堡的七座桥》的论文，圆满地解决了这一问题，同时开创了数学的一个新分支——图论。

2、问题的抽象——数学化

欧拉是如何将这生活的趣味问题转化为数学问题的呢？又是如何证明要想一次走过这七座桥是不可能的呢？欧拉的方法十分巧妙：他用点A、B、C、D表示哥尼斯堡城的四个地区C（岛区）、B（北区）、D（东区）、A（南区）；七座桥看成这四个点的连线，用1，2，3，4，5，6，7七个数字表示，如图1。

这样“七桥问题”就转化为是否能用一笔不重复地画出过此七点的图形。假设可以画出来，则图形中必有一个起点和个终点，如果这两个点不重合，则与起点或终点相交的线都必是奇数条（称奇点），如果起点与终点重合，则与之相交的线必是偶数条（称偶点），而除了起点与终点外的点也必是“偶点”。由上可知，如果一个图形可以一笔画出来，由上分析，可得如下结论，须满足如下两个条件：

（1）图形必须是连通的（图中的任一点通过一些线一定能到达其他任意一点）。

（2）图中的“奇点”数只能是0或2，我们也可依此来检验图形是否可一笔画出。回头来看看“七桥问题”，图1中的4个点全都是“奇点”，可知图不能“一笔画出”，也就是不可能不重复地通过所有的七座桥。当欧拉将这一结果发表时，震惊了当时的数学界，人们赞叹这位数学天才的创造能力！

3、引申推广

（1）过了许多年，河上又架起了第八座桥——铁路桥，如图2.这座桥的建成，使人们又想起了那有趣的问题。显然一次不重复走遍七座桥不可能，那么，如今八座桥可一次不重复走过吗？从图3可知“奇点”只有两个（D点和C点），所以可以一次不重复走过八座桥。

（2）若有一条河，河中心有两个河心岛，有15座桥把这两个岛和两岸连接起来，如图4。问能否不重复地通过所有的15座桥？按欧拉的方法，把图抽象成图5的形式，由于图中只有A、B两个“奇点”，故该图可以一笔（不重复）的画成，即可以不重复地通过所有的15座桥。

4、新学科的形成

欧拉对“哥尼斯堡七桥问题”的解决，开创了一个新的数学分支——图论。他所使用的方法是图论中常用的方法。图论原是组合数学的一个重要课题，由于发展迅速现已成了一个独立的数学分支，我们用点表示事物，用连接点的边表示事物间的联系方式，便可得到图论中的图。图论为研究任何一类离散事物的关系结构提供了一种本质的框架。他的理论已应用于经济学、心理学、社会学、遗传学、运筹学、逻辑学、语言学计算机科学等诸多领域。值得一提的是，欧拉对七桥问题的研究，后演变成多面体理论，得到了著名的欧拉公式V+F=E+2，欧拉公式是拓扑学的第一个定理。这个定理使我们看到了几何问题的一种更具深刻内涵的性质。

5、给有兴趣的读者留的问题

（1）下列图形，如图6能否一笔画？怎样画？

（2）邮路问题。

一个邮递员送信件的街道如图7所示，如果每一小段街道长1千米，那么他从邮局出发走遍所有街道再回到邮局最少要走多少千米？

6、今天的哥尼斯堡桥

哥尼斯堡的七座桥如今只剩下三座，一条新的跨河大桥已经建成，它完全跨过河心岛——内福夫岛，导游们仍向游客讲述哥尼斯堡桥的故事，有的导游甚至仍称问题没有解决，以留给游客以遐想，虽然七座哥尼斯堡桥成了历史，但是“七桥问题”留下的遗产不像这些桥那样容易破坏，欧拉卓越的解答将永载史册。