找回密码
 注册
搜索
热搜: 超星 读书 找书
查看: 1671|回复: 9

[【理工类】] 何谓“四色猜想”的计算机证明?

[复制链接]
发表于 2006-6-17 00:41:38 | 显示全部楼层 |阅读模式
我早就听说过“四色猜想”猜想,但一直对它的证明不关心,今天看了方舟子的《质疑中国哲学狂人证明四色定理》,其中写道:

众所周知,四色难题早在1976年已由美国数学家哈肯与阿佩尔借助计算机证明了。黎鸣认为,“电子计算机获得的证明是难以让人信服的,人们无法检验计算机所做出的100亿次以上的判断”,这显然是误把计算机所做的运算次数当成了证明步骤了。如果计算机运算有误,那就是硬件出了故障,只要把程序拿到别的计算机上运算,看是否有同样的结果,就可以排除硬件发生故障的可能性。
  还有一种可能性,是哈肯与阿佩尔编的证明程序中存在未发现的漏洞。这种可能性可以由别人独立地编程、验证来排除。实际上,在他们之后,也有别人改进哈肯与阿佩尔编的证明方法,独立地证明了四色定理。哈肯与阿佩尔是把地图的无限种可能情况简约为1936种构型,后来又简约为1476种,但是要靠人工一个个去验证这么多的构型是不现实的,所以才借助计算机进行验证。在1996年,罗伯森等人又进一步简约为633种构型,再用计算机验证。在2004年,沃纳和冈席尔用通用的数学证明验证程序,对罗伯森等人的证明进行了验证,肯定了其证明的正确性。至此,人们对计算机证明的最后一丝疑问,也应该可以消除了。

我对其中的“哈肯与阿佩尔是把地图的无限种可能情况简约为1936种构型,后来又简约为1476种”很感兴趣,这是如何做到的?
回复

使用道具 举报

 楼主| 发表于 2006-6-17 19:33:26 | 显示全部楼层
诚心请教,愿高人教我解疑惑
回复

使用道具 举报

发表于 2006-6-17 20:20:05 | 显示全部楼层
据我所知,四色定理的证明是用穷举法一个个情况验证的,至于约化无非是用了一些数学定理吧,不过我对这方面不清楚,希望有会员解答,解答对的愿意给两个威望奖励.
回复

使用道具 举报

发表于 2006-6-17 21:02:52 | 显示全部楼层
推荐一个四色定理的论坛

http://www.channelwest.com/bbs/forum.asp?Forum_ID=8
回复

使用道具 举报

发表于 2006-6-17 23:05:04 | 显示全部楼层
那论坛倒是不错,但是民间科学家太多了,这帮人难缠啊,我在一个地方和他们较量过,实在无聊,比如说三等分角,不可能证明我估计他们都没看过,就瞎说,一个个自以为比高斯还厉害.
回复

使用道具 举报

 楼主| 发表于 2006-6-17 23:43:31 | 显示全部楼层
谢谢调侃提供的信息,我初步看了一下,都是争先恐后“创新”的

我现在连哈肯与阿佩尔的证明都没弄清楚,还是先不管那些“创新”吧

我对方文中“哈肯与阿佩尔是把地图的无限种可能情况简约为1936种构型,后来又简约为1476种”的初步理解:
在二维平面中,所有地图组合都可以由1936或1476种构型推导出,姑且称这种推导为运算吧,这种构型之间的运算是完备的,任意两种构型的运算结果必为这1936或1476种构型之一,只有这样,用计算机证明地图的无限种可能情况才有意义。

我现在就是想弄明白我的理解对不对?
回复

使用道具 举报

发表于 2006-6-17 23:55:25 | 显示全部楼层
四色问题和图论联系颇深,还有就是几何拓扑

下面是偶从网上搬的旧兵.........
四色定理证明的基本方法是十分简单的,是经典归纳法的一个变型;如果一个地图不是四种颜色则必存在一个具有最少国家数目的反例;研究了“最小反例”的两种性质:(一)如果存在最小反例,则必存在正则地图为最小反例,(二)在正则最小反例地图中,每个国家的边界为圈。第4章从拓扑到组合,四色定理可以形成为纯组合的命题,涉及Wagner和Fary定理,Euler多面体公式,地图的对偶理论,包含了证明四色定理的完整基础和所需要的公式。第5章四色定理的组合形式,拓扑四色定理有效,而且每个平面图有一个相容的顶点4?染色,也就是把一个拓扑地图的四色问题变为一个组合图的顶点4染色问题,讨论了构型、不可约和不可避免构型。第6章约简,论述约简方法,叙述Durre-Heesch约简算法。第7章不可约集的搜索,Heesch算法涉及搜索可约构型的不可避免集合,主要有三个“障碍”,论述了解决这些障碍的规则方法。


《The Four-Color Theorem》
1998, 260pp..
Hardcover DM 69.00
ISBN:0-387-98497-6
1 Springer-Verlag
《四色定理》
鲁道夫和G.弗雷茨 著
回复

使用道具 举报

 楼主| 发表于 2006-6-18 00:07:53 | 显示全部楼层
谢谢hooker提供的信息,不过其中很多信息对我来说太专业了。我能理解“最小反例”的思路,也能理解“从拓扑到组合,四色定理可以形成为纯组合的命题”,但对“正则地图”、Wagner和Fary定理、Euler多面体公式、地图的对偶理论、组合图的顶点4染色问题等术语就一无所知了。
回复

使用道具 举报

发表于 2006-6-18 00:09:54 | 显示全部楼层
引用第7楼lkvc2006-06-18 00:07发表的“”:
谢谢hooker提供的信息,不过其中很多信息对我来说太专业了。我能理解“最小反例”的思路,也能理解“从拓扑到组合,四色定理可以形成为纯组合的命题”,但对“正则地图”、Wagner和Fary定理、Euler多面体公式、地图的对偶理论、组合图的顶点4染色问题等术语就一无所知了。
所以兄要学啊,我至少知道多面体公式.
回复

使用道具 举报

 楼主| 发表于 2006-6-18 00:21:47 | 显示全部楼层
引用第8楼长歌-废墟2006-06-18 00:09发表的“”:

所以兄要学啊,我至少知道多面体公式.
引用第9楼hooker2006-06-18 00:13发表的“”:


书名我已经提供了...........我也只能是望梅止渴.........   

多谢两位斑竹,我目前还不想改行,能弄明白最好,弄不明白也不求己过
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|网上读书园地

GMT+8, 2024-11-15 04:37 , Processed in 0.140692 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表