魔方吧·中文魔方俱乐部

标题: 世界数学难题——哥尼斯堡七桥问题 [打印本页]

作者: yeees 时间: 2011-6-16 20:24:04 标题: 世界数学难题——哥尼斯堡七桥问题

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

经过研究，欧拉发现了一笔画的规律。他认为，能一笔画的图形必须是连通图。连通图就是指一个图形各部分总是有边相连的，这道题中的图就是连通图。
但是，不是所有的连通图都可以一笔画的。能否一笔画是由图的奇、偶点的数目来决定的。那么什么叫奇、偶点呢？与奇数（单数）条边相连的点叫做奇点；与偶数（双数）条边相连的点叫做偶点。如下图中的①、④为奇点，②、③为偶点。

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

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

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

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

附件: 1.PNG (2011-6-16 20:24:04, 20.32 KB) / 下载次数 106
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ3NDU3fDZiNTQ4YTgwfDE3NjE4NTM2MjR8MHww

附件: 2.PNG (2011-6-16 20:24:04, 27.43 KB) / 下载次数 123
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ3NDU4fDM4N2Y2YWVmfDE3NjE4NTM2MjR8MHww

附件: 3.PNG (2011-6-16 20:24:04, 2.17 KB) / 下载次数 128
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ3NDU5fDRkNDg4MjM2fDE3NjE4NTM2MjR8MHww

附件: 4.PNG (2011-6-16 20:24:04, 3.38 KB) / 下载次数 110
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ3NDYwfDc1YWJhMzg4fDE3NjE4NTM2MjR8MHww

附件: 5.PNG (2011-6-16 20:24:04, 5.68 KB) / 下载次数 115
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ3NDYxfDU0OThhYjg3fDE3NjE4NTM2MjR8MHww

附件: 6.PNG (2011-6-16 20:25:42, 3.38 KB) / 下载次数 107
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ3NDYyfDQ5NGVmOGM5fDE3NjE4NTM2MjR8MHww

作者: 海上晴天 时间: 2011-6-16 21:02:53

这题很著名啊顶一个

作者: 夜雨听风 时间: 2011-6-16 21:13:05

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

作者: yeees 时间: 2011-6-16 21:25:16

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

作者: 华容道 时间: 2011-6-16 21:37:27

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

作者: 超星星 时间: 2011-6-16 22:34:00

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

作者: tm__xk 时间: 2011-6-17 01:29:51

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

作者: 今夜微凉 时间: 2011-6-17 01:33:38

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

作者: yeees 时间: 2011-7-4 13:49:42 标题: 回复 8# 的帖子

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

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

作者: csgg 时间: 2011-7-4 13:51:27

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

作者: csgg 时间: 2011-7-4 14:13:56 标题: 七桥问题新解

@@@@@@@@@@@@@@@@@@

附件: 七桥问题新解.JPG (2011-7-4 14:14:29, 95.67 KB) / 下载次数 72
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ5NDY1fDU3ZWM0YzlifDE3NjE4NTM2MjR8MHww

作者: gqc294981 时间: 2011-7-4 20:31:38

很简单啊奇点和偶点的问题么一个图里面最多有2个奇点可以 3个及以上就不可以了数学建模的入门级提醒

作者: 钟七珍 时间: 2011-7-4 23:16:08

数学历史上一道轰动一时的著名的经典难题。现在看来却是非常简单的一笔画问题。
我也是通过此题了解了一笔画。

作者: tm__xk 时间: 2011-7-5 04:11:32

标题党..
"世界数学难题"
不得不承认是事实..虽然那是n年以前的事情了..
而且"难"是指构造难..而原因是无解..
=_=||||

作者: mowxqq 时间: 2011-7-5 13:06:39

原帖由 csgg 于 2011-7-4 14:13 发表
@@@@@@@@@@@@@@@@@@

注意原题中，经过各座桥一次然后回到出发点。你的图还是有两个奇点，必然是从一个奇点出发，另一个奇点终止，只能遍历各座桥一次但并没有回到出发点，这解还是对不上原题。

[ 本帖最后由 mowxqq 于 2011-7-5 13:08 编辑 ]

作者: wskcc577 时间: 2011-7-7 09:36:05

我是个准初中生，在我上六年级的时候我在数学书上看到七桥，就和俩数学尖子生讨论了很久很久都没找到方法，结果第二天老师就跟我们说“这题无解。。。忽悠人的。。。”
10#说有解，把方法表一下~~~

作者: wskcc577 时间: 2011-7-7 09:37:49

表示11#看不懂。。。能更加简单的说吗？

作者: SURE_ 时间: 2011-7-10 16:00:15

莫不是CMO/IMO的图论么……
在二试里也可以辅助解组合题。

作者: tm__xk 时间: 2011-7-10 22:40:32

ls可以不要把cmo/imo跟图论混为一谈么..
这题的图论..跟cmo/imo神马的..级别也差的太远了吧..
-_-||

作者: 1987。 时间: 2011-7-12 01:44:05

长见识了，果断收藏。。。。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)