世界著名七桥问题

世界著名七桥问 １８世纪，沿着俄国和波兰的边界，有一条长长的布格河。这条河流经俄国的古城康尼斯堡——它就是今天俄罗斯西北边界城市加里宁格勒。 　　布格河横贯康尼斯堡城区，它有两条支流，一条称新河，另一条叫旧河，两河在城中心会合后，成为一条主流，叫做大河。在新旧两河与大河之间，夹着一块岛形地带，这里是城市的繁华地区。全城分为北、东、南、岛四个区，各区之间共有七座桥梁联系着。 人们长期生活在河畔、岛上，来往于七桥之间。有人提出这样一个问题：能不能一次走遍所有的七座桥，而每座桥只准经过一次？             问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。而利用普通数学知识，每座桥均走一次，那这七座桥所有的走法一共有7！=5040种，而这么多情况，要一一试验，这将会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？因而形成了著名的“哥尼斯堡七桥问题”。 1935年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉，请他帮忙解决这一问题。欧拉在亲自观察了哥尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七桥问题是不是原本就无解呢？ 1736年，在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新一分支---图论。 在论文中，欧拉将七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线示。并由此得到了如图一样的几何图形。 若我们分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复的画出过此七条线的问题了。若可以画出来，则图形中必有终点和起点，并且起点和终点应该是同一点，由于对称性可知由A或C为起点得到的效果是一样的，若假设以A为起点和终点，则必有一离开线和对应的进入线，若我们定义进入A的线的条数为入度，离开线的条数为出度，与A有关的线的条数为A的度，则A的出度和入度是相等的，即A的度应该为偶数。即要使得从A出发有解则A的度数应该为偶数，而实际上A的度数是3为奇数，于是可知从A出发是无解的。同时若从B或D出发，由于B、D的度数分别是5、3，都是奇数，即以之为起点都是无解的。 有上述理由可知，对于所抽象出的数学问题是无解的，即“七桥问题”也是无解的。 在18世纪，东普鲁士的首府哥尼斯堡（今属立陶宛共和国）是一座景色迷人的城市，普莱格尔河横贯城区，使这座城市锦上添花，显得更加风光旖旋。河中有两个美丽有小岛。全城被大河分割成四块陆地。河上架有七座各具特色的桥，把四块陆地像图1那样联系起来。当时许多市民都在思索如下的问题：一个散步者能否从某一陆地出发，不重复地经过每座桥一次，最后回到原来的出发地。 这就是历史上有名的哥尼斯堡七桥问题。 这个问题似乎不难解决，所以吸引了许多人都想来试试看，但是日复一日谁也没有得出确定的答案。于是有人便写信给当时著名的数学家欧拉（Euler，1707 ～1783）求教。欧拉毕竟是数学家，他并没有去重复人们已多次失败了的试验，而是首先产生了一种直觉的猜想：许多人千百次的失败，也许意味着这样的走法根本就不存在。于是欧拉把七桥问题进行了数学的抽象．用A、B、C、D四个点表示四块陆地，用两点间的一条线表示联接两块陆地之间的一座桥，就得到一个由四个点和七条线组成的图形。 于是，七桥问题就转化为一个象图2那样的图形是否可以“一笔画”的问题。什么叫“一笔画”呢？那就是笔不准离开纸，一气画成整个图形，但每一条线只许画一次，不得重复。这样的图形能不能一笔画呢？1736年欧拉证明了：答案是否定的。 为什么呢？ 因为除了起点和终点之外，我们把其余的点称为中间点。如果一个图可以一笔画的话，对于每一个中间点来说，当画笔沿某条线到达这一点时，必定要沿另一条线离开这点，并且进入这点几次，就要离开这点几次，一进一出，两两配对，所以从这点发出的线必然要是偶数条。因此，一个图形能否一笔画就有了一个判别准则： 一个可以一笔画的图形最多只能有两个点（起点和终点）与奇数条线相连。 再看图2中的四个点都是与奇数条（三条或五条）线相连的，根据这一判别准则，是不能一笔画的。 从而证明了七桥问题所的走法是不存在的。 曾经难倒许多人的七桥问题，经过欧拉这一转化，就像哥伦布竖鸡蛋一样，简单而圆满地解决了。   引申：“一笔画”问题，即由某些点和线段所组成的各种图形，能不能不重复地由一笔画成。如果图形中任意两点都可以用若干线段把它们连接起来，这样的图形称为是“连通”的，我们把凡是从图形上某点出发的线段数目是奇数的，称为奇点；是偶数的，称为偶点。能够一笔画成的图形只有下面两种情况：     （1）图形中所有的点都是偶点，就可以从图形的任意一点出发一笔画成；     （2）图形中只有两个奇点，可以从其中一个奇点出发一笔画成。 在这里，我们可以看到欧拉解决这个问题的关键就是把“七桥问题”变成了一个“一笔画”问题，那么，欧拉又是怎样完成这一转变的呢？ 他把岛、半岛和陆地的具体属性舍去，而仅仅留下与问题有关的东西，这就是四个几何上的“点”；他再把桥的具体属性排除，仅留下一条几何上的“线”，然后，把“点”与“线”结合起来，这样就实现了从客观事物到图形的转变。我们把得到“点”和“线”的思维方法叫做抽象，把由“点”和“线”结合成图形的思维方法叫做概括。所谓抽象就是从客观事物中排除非本质属性，透过现象抽出本质属性的思维方法。概括就是将个别事物的本质属性结合起来的思维方法。