七桥问题来源

8世纪初，普鲁士的哥尼斯堡（现俄罗斯加里宁格勒），有一条名叫Pregel的河流横经其中，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如下图）。

当地的市民正从事一项非常有趣的消遣活动，在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。

这项消遣活动被归纳成下面的问题提交到大数学家欧拉那里。

问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。

736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，将它转化成一个几何问题——一笔画问题。欧拉不仅解决了这个问题，同时开创了数学的一个新的分支——图论与几何拓扑，也由此展开了数学史上的新历程。

欧拉创新性的问题论证

欧拉发现当地居民有一项消遣活动，就是试图每座桥恰好走过一遍并回到原出发点，但从来没人成功过。

欧拉证明了这种走法是不可能的。现在看来，欧拉的证明过程非常简单，但他对七桥问题的抽象和论证思想，开创了一个新的学科：图论(Graph)。如今，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。图论还是计算机科学的数据结构和算法中最重要的框架（没有之一）。

首先能想到的证明方法是把走七座桥的走法都列出来，一个一个的试验，但七座桥的所有走法共用7！＝5040种，逐一试验将是很大的工作量。欧拉作为数学家，当然没那样想。欧拉把两座岛和河两岸抽象成顶点，每一座桥抽象成连接顶点的一条边，那么哥尼斯堡的七座桥就抽象成下面的图：

假设每座桥都恰好走过一次，那么对于A、B、C、D四个顶点中的每一个顶点，需要从某条边进入，同时从另一条边离开。进入和离开顶点的次数是相同的，即每个顶点有多少条进入的边，就有多少条出去的边，也就是说，每个顶点相连的边是成对出现的，即每个顶点的相连边的数量必须是偶数。而上图中A、C、D四个顶点的相连边都是3，顶点D的相连边为5，都为奇数。因此，这个图无法从一个顶点出发，遍历每条边各一次。

简单地说，连到一点的数目如是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端。也就是说：没有办法不重复、不遗漏的一次走完七座桥。

对于一个给定的连通图，如果存在两个以上（不包括两个）奇顶点，那么满足要求的路线便不存在了，且有n个奇顶点的图至少需要n/2笔画出。如果只有两个奇顶点，则可从其中任何一地出发完成一笔画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。

欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。欧拉就把七桥问题转化把它转化成一个几何问题——一笔画问题了。然后，七桥问题解决了，《哥尼斯堡的七座桥》的论文出来了。然后，一个新的数学分支——图论与几何拓扑开创了，数学史上的新历程开始了。然后，靠我们了……，这里的关键，是欧拉把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。

这里，借用了图学思维——图形的简化和数学思维——数学抽象。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。什么是“去粗取精、去伪成真”？这就是。什么是“复杂事情简单化”？这就是。这个案例，试图去表述：如何将一个实际问题转化成一个抽象问题。

演绎图学思维简化问题的步骤，而后上升到数学抽象，变成一个纯数学问题的过程。

欧拉的证明与其说是数学证明，还不如看作是一个逻辑证明。一个曾难住那么多人的问题，竟然是这样一个简单的出人意料的推理，还开创了一个新的学科。欧拉非常巧妙的把一个实际问题抽象成一个合适的数学模型，这种研究方法就是我们应该掌握的数学模型方法。这并不需要运用多么深奥的理论，但能想到这一点，却是解决问题的关键。

解决了这个简单的七桥问题并没有让大数学家欧拉停止探索的脚步。他想要研究更加一般性的问题，也就是对任意一个图形能否一笔画把它画出来。

结论是：

（1）如果图形是连通的，并且顶点全部是偶顶点（即奇顶点的个数为0），那么，可以一笔画出图形，且起点可以是图形中任意一个顶点。（这时的一笔画路径是一条封闭的曲线，顶点位于这条闭曲线上。自然，从哪个点出发都是可以走回到起点的。）

（2）如果图形是连通的且有两个奇顶点，则可以一笔画出图形，起点是这两个奇顶点中的任意一个，终点必定是另一个奇顶点。（从偶顶点出发是不能一笔画出整个图形的。）

（3）如果奇顶点的个数不止两个，则我们不能一笔画出整个图形。（图形中若有奇顶点，则它们一定是起点或终点。一个可以一笔画出的图形只能有一个起点和一个终点。所以，奇顶点不能超过两个。我们这里所说的不能画出是绝对的不能，不用试。）

欧拉从七桥问题出发，完美解决了一笔画问题。哪怕是比七桥问题复杂很多的由几十座桥甚至上百座桥构成的河-桥体系中（也就是由几十条甚至上百条弧线构成的图形中），我们都能够在不长的时间内（几分钟足矣）判断出这个图形能否一笔画出。具体怎么画，欧拉认为不是什么大问题。

通过思考实际问题和上述解决方案，我们触及了图理论的基本概念（节点，边，有向，无向），避免了只有枯燥的理论。然而我们还未完全解决欧拉图和上述问题。我们现在应该转向图的计算机表示，因为这对我们程序员来说是最重要的。通过在计算机程序中表示图，我们能设计一个标记图路径的算法，从而确定它是否是欧拉路径。

七桥问题带给人们的思考

现在大部分孩子在学习数学知识的时候，光顾着背公式记答案，完全没有考虑到抛开数字本身看问题本质的重要性，导致数学这门课举步维艰，心存怯意。数学是一门很好玩的课程，只要多问几个为什么，理解每一个原理和基础知识的来龙去脉，学会从知识的关联性上看问题，掌握数形结合，就一定可以在这门课上走得很远。

数学与物理学有很大的不同，假如说物理学是学知识，那么数学则是学思维。如果数学思维掌握了，数学就能很快打通全身经脉，实现自我运行。可惜现在的教育模式只是在乱贴膏药，舍本逐末，把最不需要记忆或者背诵的课程硬生生地变成了语文课。中国奥数教父单墫教授曾在一本给初中生写的书中说到：“学数学，不是为了当熟练的‘操作工’、‘模仿秀’，而是为了学会思考。大量重复的练习，不利于培养学习的兴趣，甚至会弄坏了学习的‘胃口’。”