世界数学难题——哥尼斯堡七桥问题

yeees

    18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥。将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。 这就是哥尼斯堡七桥问题，一个著名的图论问题。
    1727年在欧拉20岁的时候，被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究。他的德国朋友告诉了他这个曾经令许多人困惑的问题。
    欧拉并没有跑到哥尼斯堡去走走。他把这个难题化成了这样的问题来看：把二岸和小岛缩成一点，桥化为边，于是“七桥问题”就等价于下图中所画图形的一笔画问题了， 这个图如果能够一笔画成的话，对应的“七桥问题”也就解决了。
   
    经过研究，欧拉发现了一笔画的规律。他认为，能一笔画的图形必须是连通图。连通图就是指一个图形各部分总是有边相连的，这道题中的图就是连通图。
    但是，不是所有的连通图都可以一笔画的。能否一笔画是由图的奇、偶点的数目来决定的。那么什么叫奇、偶点呢？与奇数（单数）条边相连的点叫做奇点；与偶数（双数）条边相连的点叫做偶点。如下图中的①、④为奇点，②、③为偶点。

1．凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。例如下图都是偶点，画的线路可以是：①→③→⑤→⑦→②→④→⑥→⑦→①

2．凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。例如下图的线路是：①→②→③→①→④

3．其他情况的图都不能一笔画出。


[ 本帖最后由 yeees 于 2011-6-16 20:25 编辑 ]

海上晴天

这题很著名啊 顶一个

夜雨听风

终于懂了什么情况下才能一笔画

yeees

其实我又想到了盲解三阶魔方中的奇偶变换。。。

华容道

很著名的问题！小学时让我思索许久的一道题……

超星星

离散数学就有这题是例题，今天我们还说了这题的的，以及欧拉图

tm__xk

我只能说..我只是来看上色的....

今夜微凉

哇哈哈，楼主可以把四色地图问题一起找出来说说

yeees

原帖由 今夜微凉 于 2011-6-17 01:33 发表
哇哈哈，楼主可以把四色地图问题一起找出来说说

嘿嘿，都是经典的数学问题。

csgg

这问题有解，比较BT………………